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.

    SubdivisionOfPointsMethod
    SubdivisionOfPoints(points, cells)

    Arguments

    • 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.

    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 = SubdivisionOfPoints(moaepts, moaeimnonreg0)
    A subdivision of points in ambient dimension 3
    source
    SubdivisionOfPointsMethod
    SubdivisionOfPoints(points, weights)

    Arguments

    • 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 = SubdivisionOfPoints(moaepts, [1,1,1,1,1,1])
    A 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.

    Saving and loading

    Objects of type SubdivisionsOfPoints can be saved to a file and loaded from a file in the following way:

    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> moaeincidence = 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 = SubdivisionOfPoints(moaepts, moaeincidence)
    A subdivision of points in ambient dimension 3
    
    julia> save("moae.sop", MOAE);
    
    julia> SOP = load("moae.sop");
    
    julia> is_regular(SOP)
    false
    

    The file is in JSON format and contains all previously gathered data belonging to the underlying polymake object. In particular, this file can now be read by both polymake and OSCAR.

    Auxiliary functions

    ambient_dimMethod
    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 = SubdivisionOfPoints(moaepts, [1,1,1,1,1,1]);
    
    julia> ambient_dim(SOP)
    3
    source
    is_regularMethod
    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 = IncidenceMatrix([[4,5,6],[1,4,2],[2,4,5],[2,3,5],[3,5,6],[1,3,6],[1,4,6]]);
    
    julia> MOAE = SubdivisionOfPoints(moaepts, moaeimnonreg0);
    
    julia> is_regular(MOAE)
    false
    
    julia> SOP = SubdivisionOfPoints(moaepts, [1,1,1,1,1,1]);
    
    julia> is_regular(SOP)
    true
    source
    maximal_cellsFunction
    maximal_cells(SOP::SubdivisionOfPoints)

    Return an iterator over 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 = SubdivisionOfPoints(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]
    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 = SubdivisionOfPoints(moaepts, [1,1,1,1,1,1])
    A subdivision of points in ambient dimension 3
    
    julia> maximal_cells(IncidenceMatrix, SOP)
    1×6 IncidenceMatrix
    [1, 2, 3, 4, 5, 6]
    source
    min_weightsFunction
    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 = SubdivisionOfPoints(moaepts, [1,1,1,1,1,1]);
    
    julia> min_weights(SOP)
    pm::Vector<long>
    0 0 0 0 0 0
    source
    n_maximal_cellsMethod
    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 = SubdivisionOfPoints(moaepts, [1,1,1,1,1,1]);
    
    julia> n_maximal_cells(SOP)
    1
    source
    pointsMethod
    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. ```jldoctest 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 = SubdivisionOfPoints(moaepts, moaeimnonreg0);

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

    source
    secondary_coneFunction
    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 = IncidenceMatrix([[4,5,6],[1,4,2],[2,4,5],[2,3,5],[3,5,6],[1,3,6],[1,4,6]]);
    
    julia> MOAE = SubdivisionOfPoints(moaepts, moaeimnonreg0)
    A subdivision of points in ambient dimension 3
    
    julia> C = secondary_cone(MOAE)
    A polyhedral cone in ambient dimension 6
    
    julia> dim(C)
    4
    source