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
— Methodsubdivision_of_points([f = QQFieldElem,] points, cells)
Arguments
f::Union{Type{T}, Field}
: either specifies theType
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.
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 = IncidenceMatrix([[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
subdivision_of_points
— Methodsubdivision_of_points([f = QQFieldElem,] points, weights)
Arguments
f::Union{Type{T}, Field}
: either specifies theType
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
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
— Methodambient_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
is_regular
— Methodis_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 = IncidenceMatrix([[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
maximal_cells
— Functionmaximal_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 = IncidenceMatrix([[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]
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]
min_weights
— Functionmin_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
n_maximal_cells
— Methodn_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
points
— Methodpoints(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 = IncidenceMatrix([[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]
secondary_cone
— Functionsecondary_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 = IncidenceMatrix([[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