Subdivisions of Points

Introduction

Let $\mathbb{F}$ be an ordered field; the default is that $\mathbb{F}=\mathbb{Q}$ is the field of rational numbers and other fields are not yet supported everywhere in the implementation.

A subdivision of points consists of

a finite set $\mathcal{P}\subseteq\mathbb{F}^n$ of points; and
a finite set of cells $\mathcal{S}\subseteq 2^{\mathcal{P}}$.

The cells are only allowed to intersect in common faces. In contrast to the maximal cones of a polyhedral fan or the maximal polytopes of a polyhedral complex, cells are allowed to have interior points here, i.e. they are not given in terms of their vertices.

Construction

There are two ways to construct a subdivision of points. First, one can specify the cells directly. Second, one can assign a weight or height to every point, take the convex hull and take the cells corresponding to facets visible from below ("lower envelope"). Not every subdivision of points comes from a weight vector, but if it does, it is called regular.

subdivision_of_points — Method

subdivision_of_points([f = QQFieldElem,] points, cells)

Arguments

f::Union{Type{T}, Field}: either specifies the Type of its coefficients or their

parent Field.

points::AbstractCollection[PointVector]: Points generating the cells of the subdivision; encoded row-wise as representative vectors.
cells::IncidenceMatrix: An incidence matrix; there is a 1 at position (i,j) if cell i contains point j, and 0 otherwise.

A subdivision of points formed from points and cells made of these points. The cells are given as an IncidenceMatrix, where the columns represent the points and the rows represent the cells.

Warning

It is required, but not checked, that the cells cover the convex hull of the points. Likewise it is not checked that the cells form a proper polyhedral complex.

Examples

The following is the famous "mother of all examples" (MOAE) non-regular triangulation.

julia> moaepts = [4 0 0; 0 4 0; 0 0 4; 2 1 1; 1 2 1; 1 1 2];

julia> moaeimnonreg0 = incidence_matrix([[4,5,6],[1,4,2],[2,4,5],[2,3,5],[3,5,6],[1,3,6],[1,4,6]]);

julia> MOAE = subdivision_of_points(moaepts, moaeimnonreg0)
Subdivision of points in ambient dimension 3

source

subdivision_of_points — Method

subdivision_of_points([f = QQFieldElem,] points, weights)

Arguments

f::Union{Type{T}, Field}: either specifies the Type of its coefficients or their

parent Field.

points::AbstractCollection[PointVector]: Points generating the cells of the subdivision; encoded row-wise as representative vectors.
weights::AbstractVector: A vector with one entry for every point indicating the height of this point.

A subdivision of points formed by placing every point at the corresponding height, then taking the convex hull and then only considering those cells corresponding to faces visible from below ("lower envelope").

Examples

We use the MOAE points, but give a weight vector instead of cells:

julia> moaepts = [4 0 0; 0 4 0; 0 0 4; 2 1 1; 1 2 1; 1 1 2];

julia> SOP = subdivision_of_points(moaepts, [1,1,1,1,1,1])
Subdivision of points in ambient dimension 3

julia> n_maximal_cells(SOP)
1

source

From a subdivision of points one can construct the secondary_cone(SOP::SubdivisionOfPoints), i.e. the cone that is the closure of the set of all weight vectors realizing that subdivision.

Auxiliary functions

ambient_dim — Method

ambient_dim(SOP::SubdivisionOfPoints)

Return the ambient dimension SOP, which is the dimension of the embedding space.

Examples

The ambient dimension of the MOAE is 3, independent of the subdivision chosen.

julia> moaepts = [4 0 0; 0 4 0; 0 0 4; 2 1 1; 1 2 1; 1 1 2];

julia> SOP = subdivision_of_points(moaepts, [1,1,1,1,1,1]);

julia> ambient_dim(SOP)
3

source

is_regular — Method

is_regular(SOP::SubdivisionOfPoints)

Determine whether SOP is regular, i.e. can be given via a height function.

Examples

This is the so-called "mother of all examples", a very famous non-regular triangulation of six points.

julia> moaepts = [4 0 0; 0 4 0; 0 0 4; 2 1 1; 1 2 1; 1 1 2];

julia> moaeimnonreg0 = incidence_matrix([[4,5,6],[1,4,2],[2,4,5],[2,3,5],[3,5,6],[1,3,6],[1,4,6]]);

julia> MOAE = subdivision_of_points(moaepts, moaeimnonreg0);

julia> is_regular(MOAE)
false

julia> SOP = subdivision_of_points(moaepts, [1,1,1,1,1,1]);

julia> is_regular(SOP)
true

source

maximal_cells — Function

maximal_cells(SOP::SubdivisionOfPoints)

Return an iterator over the maximal cells of SOP.

Optionally IncidenceMatrix can be passed as a first argument to return the incidence matrix specifying the maximal cells of SOP.

Examples

Display the cells of the "mother of all examples" non-regular triangulation.

julia> moaepts = [4 0 0; 0 4 0; 0 0 4; 2 1 1; 1 2 1; 1 1 2]
6×3 Matrix{Int64}:
 4  0  0
 0  4  0
 0  0  4
 2  1  1
 1  2  1
 1  1  2

julia> moaeimnonreg0 = incidence_matrix([[4,5,6],[1,4,2],[2,4,5],[2,3,5],[3,5,6],[1,3,6],[1,4,6]])
7×6 IncidenceMatrix
[4, 5, 6]
[1, 2, 4]
[2, 4, 5]
[2, 3, 5]
[3, 5, 6]
[1, 3, 6]
[1, 4, 6]


julia> MOAE = subdivision_of_points(moaepts, moaeimnonreg0);

julia> maximal_cells(MOAE)
7-element SubObjectIterator{Vector{Int64}}:
 [4, 5, 6]
 [1, 2, 4]
 [2, 4, 5]
 [2, 3, 5]
 [3, 5, 6]
 [1, 3, 6]
 [1, 4, 6]

julia> maximal_cells(IncidenceMatrix, MOAE)
7×6 IncidenceMatrix
[4, 5, 6]
[1, 2, 4]
[2, 4, 5]
[2, 3, 5]
[3, 5, 6]
[1, 3, 6]
[1, 4, 6]

source

maximal_cells(IncidenceMatrix, SOP::SubdivisionOfPoints)

Return the maximal cells of SOP as an incidence matrix.

The rows of the output correspond to the maximal cells and the columns correspond to the cells.

Examples

If we give all points the same weight there is only one cell containing all points.

julia> moaepts = [4 0 0; 0 4 0; 0 0 4; 2 1 1; 1 2 1; 1 1 2]
6×3 Matrix{Int64}:
 4  0  0
 0  4  0
 0  0  4
 2  1  1
 1  2  1
 1  1  2

julia> SOP = subdivision_of_points(moaepts, [1,1,1,1,1,1])
Subdivision of points in ambient dimension 3

julia> maximal_cells(IncidenceMatrix, SOP)
1×6 IncidenceMatrix
[1, 2, 3, 4, 5, 6]

source

min_weights — Function

min_weights(SOP::SubdivisionOfPoints)

Return the minimal weights inducing a subdivision of points. This method will give an error if the input subdivision is non-regular.

Examples

If all points have the same weight, then the 0-vector is minimal.

julia> moaepts = [4 0 0; 0 4 0; 0 0 4; 2 1 1; 1 2 1; 1 1 2];

julia> SOP = subdivision_of_points(moaepts, [1,1,1,1,1,1]);

julia> min_weights(SOP)
6-element Vector{Int64}:
 0
 0
 0
 0
 0
 0

source

n_maximal_cells — Method

n_maximal_cells(SOP::SubdivisionOfPoints)

Return the number of maximal cells of SOP.

Examples

If all points have the same weight, there is only one cell.

julia> moaepts = [4 0 0; 0 4 0; 0 0 4; 2 1 1; 1 2 1; 1 1 2];

julia> SOP = subdivision_of_points(moaepts, [1,1,1,1,1,1]);

julia> n_maximal_cells(SOP)
1

source

points — Method

points(SOP::SubdivisionOfPoints)

Return the points of the subdivision of points, SOP.

Examples

Display the points of the "mother of all examples" non-regular triangulation.

julia> moaepts = [4 0 0; 0 4 0; 0 0 4; 2 1 1; 1 2 1; 1 1 2];

julia> moaeimnonreg0 = incidence_matrix([[4,5,6],[1,4,2],[2,4,5],[2,3,5],[3,5,6],[1,3,6],[1,4,6]]);

julia> MOAE = subdivision_of_points(moaepts, moaeimnonreg0);

julia> points(MOAE)
6-element SubObjectIterator{PointVector{QQFieldElem}}:
 [4, 0, 0]
 [0, 4, 0]
 [0, 0, 4]
 [2, 1, 1]
 [1, 2, 1]
 [1, 1, 2]

source

secondary_cone — Function

secondary_cone(SOP::SubdivisionOfPoints)

Return the secondary cone of a subdivision of points, the closure of all the weight vectors inducing the given subdivision of points.

Examples

For a non-regular subdivision, the secondary cone can still contain non-trivial weights, but it will not be full-dimensional.

julia> moaepts = [4 0 0; 0 4 0; 0 0 4; 2 1 1; 1 2 1; 1 1 2];

julia> moaeimnonreg0 = incidence_matrix([[4,5,6],[1,4,2],[2,4,5],[2,3,5],[3,5,6],[1,3,6],[1,4,6]]);

julia> MOAE = subdivision_of_points(moaepts, moaeimnonreg0)
Subdivision of points in ambient dimension 3

julia> C = secondary_cone(MOAE)
Polyhedral cone in ambient dimension 6

julia> dim(C)
4

source