Subpolygons

cls_cone_normal_form(A :: Matrix2{T}) where {T <: Integer}

Bring a two-dimensional cone into normal form in the sense of [6]. The result is a triple (d, k, M), where d and k are the parameters of the cone and M is a 2x2 integral matrix such that M * [0 d ; 1 -k] == A

Example

julia> A = Matrix2(2, 1, -3, -5)
2×2 SMatrix{2, 2, Int64, 4} with indices SOneTo(2)×SOneTo(2):
 2  -3
 1  -5

julia> cls_cone_normal_form(A)
(7, 5, [1 2; 0 1])

hirzebruch_jung(x :: T, y :: T) where {T <: Integer}

Return the Hirzebruch-Jung continued fraction associated to x // y.

Example

See Example 10.2.4 of [6].

julia> hirzebruch_jung(7,5)
3-element Vector{Int64}:
 2
 2
 3

hilbert_basis(A :: Matrix2{T}) where {T <: Integer}

Return the hilbert basis of a two-dimensional cone spanned by the columns of A, which must be primitive.

Example

See Example 10.2.4 of [6].

julia> A = Matrix2(0,1,7,-5)
2×2 SMatrix{2, 2, Int64, 4} with indices SOneTo(2)×SOneTo(2):
 0   7
 1  -5

julia> hilbert_basis(A)
5-element Vector{SVector{2, Int64}}:
 [0, 1]
 [1, 0]
 [2, -1]
 [3, -2]
 [7, -5]

hilbert_basis(v1 :: LatticePoint{T}, v2 :: LatticePoint{T}) where {T <: Integer}

Return the hilbert basis of a two-dimensional cone spanned by given integral primitive vectors v1 and v2.

remove_vertex(P :: RationalPolygon{T}, i :: Int) where {T <: Integer}

Return a pair (Q, keeps_genus), where Q is the convex hull of all k-rational points of P except the i-th vertex and keeps_genus :: Bool is true if and only if Q has the same number of interior lattice points as P. If the argument primitive = true is passed, the convex hull is taken of all primitive k-rational points of P except the i-th vertex.

Example

Compare Example 10.2.7 of [6].

julia> P = convex_hull(LatticePoint{Int}[(0,0),(7,-5),(7,1),(0,1)])
Rational polygon of rationality 1 with 4 vertices.

julia> Q,_ = remove_vertex(P,1)
(Rational polygon of rationality 1 with 4 vertices., false)

julia> vertices(Q)
4-element Vector{SVector{2, Rational{Int64}}}:
 [0, 1]
 [3, -2]
 [7, -5]
 [7, 1]

SubpolygonStorage{T <: Integer}

An abstract supertype of storage options for computing subpolygons. There are two subtypes InMemorySubpolygonStorage and HDFSubpolygonStorage. The former keeps all subpolygons in memory, the latter delegeates their storage to the disk using the HDF5 format. Both implement subpolygons_single_step.

struct InMemorySubpolygonStoragePreferences{T <: Integer}

A struct holding preferences for InMemorySubpolygonStorage. There are the following fields:

• primitive :: Bool: Whether only subpolygons with primitive vertices should be computed. The default is false.
• use_affine_normal_form :: Bool: Whether to use affine_normal_form or unimodular_normal_form. The default is true, i.e. affine normal form.
• only_equal_number_of_interior_lattice_points :: Bool: Whether only subpolygons having the same number of interior lattice points as the starting polygons should be computed. The default is false.
• exclude_very_thin_polygons: Whether polygons that can be realized in $\mathbb{R} \times [0,1]$ should be excluded. This is only relevant for polygons with no interior lattice points. The default is false.

mutable struct InMemorySubpolygonStorage{T <: Integer} <: SubpolygonStorage{T}

A struct holding results of a subpolygon computation. It has the following fields:

• preferences :: InMemorySubpolygonStoragePreferences{T}
• polygons :: Dict{T,Set{RationalPolygon{T}}}
• last_completed_area :: T
• total_count :: Int

struct HDFSubpolygonStoragePreferences{T <: Integer}

A struct holding preferences for HDFSubpolygonStorage. There are the following fields:

• rationality :: T: The rationality of the polygons. The default is one(T).
• primitive :: Bool: Whether only subpolygons with primitive vertices should be computed. The default is false.
• use_affine_normal_form :: Bool: Whether to use affine_normal_form or unimodular_normal_form. The default is true, i.e. affine normal form.
• only_equal_number_of_interior_lattice_points :: Bool: Whether only subpolygons having the same number of interior lattice points as the starting polygons should be computed. The default is false.
• exclude_very_thin_polygons: Whether polygons that can be realized in $\mathbb{R} \times [0,1]$ should be excluded. This is only relevant for polygons with no interior lattice points. The default is false.
• block_size :: Int: How many polygons should be read into memory at once during the shaving process. Defaults to 10^6.
• maximum_number_of_vertices :: Int: An upper bound for the maximal number of vertices to be expected in the computation. This has to be set since every HDF5 file generated will have a dataset "numbers_of_polygons" storing the number of polygons for each number of vertices and the size of this dataset needs to be set beforehand. Defaults to 100, which should be more than enough for any feasable computation.
• swmr :: Bool: Whether to use single-reader-multiple-writer mode for HDF5. Defaults to true.

mutable struct HDFSubpolygonStorage{T <: Integer} <: SubpolygonStorage{T}

A struct for managing the result of a subpolygon computation using the HDF5 file format. It has the following fields:

• preferences :: HDFSubpolygonStoragePreferences{T}
• file_path :: String: The file path of the HDF5 file to be created.
• group_path :: String: Path to a group within the HDF5 file, if it already exists. Defaults to "/", i.e. the root group.
• hash_sets :: Dict{T,Set{UInt128}}: A dictionary of hashes of polygons already encountered. This is used for comparison with new polygons to ensure the result contains each polygon exactly once. We hold these hashes in memory to avoid needing to read in polygons that have been written out in the past, which saves a lot of time.
• last_completed_area :: T: The last area that has been completed. This counts down from the maximum area of the starting polygons to 1.
• total_count :: Int

initialize_subpolygon_storage(st :: HDFSubpolygonStorage{T}, Ps :: Vector{<:RationalPolygon{T}}) where {T <: Integer}

Initialize a newly created HDFSubpolygonStorage with a given set of starting polygons. To restart an interrupted computation, see also restore_hdf_subpolygon_storage_status.

subpolygons_single_step(st :: InMemorySubpolygonStorage{T}; logging :: Bool = false) where {T <: Integer}

Perform a single step of a subpolygon computation in memory.

subpolygons_single_step(st :: HDFSubpolygonStorage{T}; logging :: Bool = false) where {T <: Integer}

Perform a single step in a subpolygon computation using the HDF5 file format.

subpolygons(st :: SubpolygonStorage{T}; logging :: Bool = false) where {T <: Integer}

Compute all subpolygons with the given storage option.

subpolygons(Ps :: Vector{<:RationalPolygon{T}}) where {T <: Integer}
subpolygons(P :: RationalPolygon{T}) where {T <: Integer}

Compute all subpolygons of a rational polygon or list of rational polygons. The computation is done in memory, for storage on disk see also HDFSubpolygonStorage. This function takes the following keyword arguments:

• primitive :: Bool: Whether only subpolygons with primitive vertices should be returned. The default is false.
• use_affine_normal_form :: Bool: Whether to use affine or unimodular normal form. The default is true, so affine normal form.
• only_equal_number_of_interior_lattice_points :: Bool: Whether only subpolygons that share the same number of interior lattice points with the starting polygons should be returned.
• logging :: Bool: Whether to display logging messages about the computation progress.

Example

There are 148 subpolygons of the square of side length 3, up to affine equivalence. The maximal number of vertices of those is 8, attained by exactly one polygon.

julia> Ps = subpolygons(convex_hull(LatticePoint{Int}[(0,0),(3,0),(0,3),(3,3)]));

julia> length(Ps)
148

julia> maximum(number_of_vertices.(Ps))
8

restore_hdf_subpolygon_storage_status(st :: HDFSubpolygonStorage{T}) where {T <: Integer}

Restore a subpolygons computation's status that was interrupted from an HDF5 file. All polygons will be read in, hashed and saved into st.hash_sets. Moreover, st.last_completed_area and st.total_count will be properly set. After calling this function, the computation can be resumed by calling subpolygons(st) again.