NTFE enumeration¶

Return the cone of heights inducing given 2-face triangulations.

Given triangulations of (some of) the 2-faces of a polytope, construct the cone whose strict interior consists of the height vectors whose induced regular subdivision restricts to the given triangulation on each of these 2-faces. The height vectors have one entry per lattice point of the polytope, indexed by point label.

This is akin to the expanded secondary cone (see ntfe_cones), except that some 2-faces may be left free, which is why the more generic name is used. Duplicate inequalities are removed.

Parameters:

• triangs (list[Triangulation | None]) –

  The triangulations of the 2-faces to enforce, with points labelled as in the ambient polytope (e.g. as returned by face_triangs). None entries are skipped, leaving the corresponding 2-face free.

• npts (int) –

  The number of lattice points of the polytope. This is the ambient dimension of the cone.

• poly (Polytope | None, default: None ) –

  The ambient polytope. Only used, and then required, if require_star is true.

• require_star (bool, default: False ) –

  Whether to also include the inequalities enforcing starness of the resulting triangulation. This is usually not recommended, as triangulations can be made star simply by lowering the height of the origin. It is only recommended if the cone (or related ones, like the Kahler cone) is of independent interest.

• dense (bool, default: False ) –

  Whether to return the hyperplanes as a dense array instead of a sparse matrix. Only used if as_cone is false.

• big_ints (bool, default: False ) –

  Whether to convert dense hyperplanes to the default (64-bit) integer type instead of the 16-bit type used internally. Only used if dense is true and as_cone is false.

• as_cone (bool, default: True ) –

  Whether to return a Cone object instead of its hyperplanes.

• verbosity (int, default: 0 ) –

  The verbosity level.

Returns:

• Cone | csr_matrix | ndarray –

  The cone, or its inward-facing hyperplane normals (one per row) as a sparse matrix or, if dense is true, as a dense array.

Raises:

• ValueError –

  If require_star is true but poly is not specified.

Examples:

We construct the cone of heights that induce the first FRT of each 2-face, and check that it is solid.

>>> from cytools import Polytope
>>> from cytools.ntfe import cone_of_permissible_heights
>>> p = Polytope([[1,-1,-2,1],[1,-1,0,-1],[-1,0,1,1],[-1,2,1,-1],[1,0,0,0],
...               [-1,0,0,0],[0,0,0,1],[0,0,1,0],[0,1,0,0],[0,1,1,-1]])
>>> triangs = [ft[0] for ft in p.face_triangs()]
>>> c = cone_of_permissible_heights(triangs, len(p.labels))
>>> print(c)
A rational polyhedral cone in RR^13 defined by 6 hyperplanes
>>> c.is_solid()
True

Source on GitHub

Return the support of the expanded secondary fan.

This is the cone of all height vectors that induce fine, regular triangulations (FRTs) of every 2-face of the polytope (emphasis on fine). Equivalently, it is the union of all expanded secondary cones (see ntfe_cones). It is called the "expanded" (rather than "plain") secondary fan because only 2-face information is used. The height vectors have one entry per lattice point of the polytope, indexed by point label. See arXiv:2309.10855 for details.

This function is attached to Polytope as the method expanded_secondary_fan, where self is the polytope.

Parameters:

• dense (bool, default: False ) –

  Whether to return the hyperplanes as a dense array instead of a sparse matrix. Only used if as_cone is false.

• big_ints (bool, default: False ) –

  Whether to convert dense hyperplanes to the default (64-bit) integer type instead of the 16-bit type used internally. Only used if dense is true and as_cone is false.

• as_cone (bool, default: True ) –

  Whether to return a Cone object instead of its hyperplanes.

Returns:

• Cone | csr_matrix | ndarray –

  The support of the expanded secondary fan, or its inward-facing hyperplane normals (one per row) as a sparse matrix or, if dense is true, as a dense array.

Examples:

>>> from cytools import Polytope
>>> p = Polytope([[1,-1,-2,1],[1,-1,0,-1],[-1,0,1,1],[-1,2,1,-1],[1,0,0,0],
...               [-1,0,0,0],[0,0,0,1],[0,0,1,0],[0,1,0,0],[0,1,1,-1]])
>>> print(p.expanded_secondary_fan())
A rational polyhedral cone in RR^13 defined by 7 hyperplanes

Source on GitHub

Return (some of) the expanded secondary cones of the polytope.

Each choice of one FRT per 2-face defines an expanded secondary cone (see ntfe_hypers). The cones are not checked for solidity; the solid ones correspond to the NTFEs. See arXiv:2309.10855 for details.

This function is attached to Polytope as the method ntfe_cones, where self is the polytope.

Parameters:

• hypers (list[ArrayLike] | None, default: None ) –

  The hyperplanes defining the cones, e.g. as returned by ntfe_hypers. If not specified, they are computed with ntfe_hypers.

• require_star (bool, default: False ) –

  Whether to also include the inequalities enforcing starness. This is not recommended unless such cones are of direct interest. If one only cares about NTFE FRSTs, it is more efficient to enforce starness when constructing the triangulation, by lowering the height of the origin (i.e. with make_star=True).

• N (int | None, default: None ) –

  The number of cones to return. If hypers is not specified, this many distinct choices of 2-face FRTs are sampled by ntfe_hypers. Otherwise, N of the given hyperplanes are picked at random (this is ignored if as_generator is true). If not specified, all cones are returned.

• seed (int | None, default: None ) –

  The random seed used when sampling. If not specified, Python's default seeding (from system randomness or the current time) is used. Note that this reseeds Python's global random module.

• face_ineqs (list[list[csr_matrix]] | None, default: None ) –

  The CPL inequalities of each FRT of each 2-face, as returned by triangface_ineqs. If not specified, they are computed.

• face_triangs (list[list[Triangulation]] | None, default: None ) –

  The FRTs of each 2-face, as returned by face_triangs. Only used if face_ineqs is not specified. If not specified, they are computed.

• max_npts (int, default: 17 ) –

  The maximum number of lattice points of a 2-face for which all FRTs are enumerated (if face_triangs is not specified). For 2-faces with more points, FRTs are only sampled.

• N_face_triangs (int, default: 1000 ) –

  The maximum number of FRTs to sample for each 2-face with more than max_npts points (if face_triangs is not specified).

• triang_method (str, default: 'grow2d' ) –

  The method used to sample FRTs of 2-faces with more than max_npts points (if face_triangs is not specified). The options are "fast", "fair", "grow2d", and "dualgnn"; see face_triangs.

• as_generator (bool, default: False ) –

  Whether to return a generator instead of a list. Use this if memory is a concern.

• separate_boring (bool, default: True ) –

  Currently not passed on to ntfe_hypers, so it has no effect.

• verbosity (int, default: 0 ) –

  The verbosity level.

Returns:

• list[Cone] | Generator[Cone, None, None] –

  The expanded secondary cones.

Examples:

We compute the expanded secondary cones of a polytope and count how many of them are solid, i.e. how many NTFEs there are.

>>> from cytools import Polytope
>>> p = Polytope([[1,-1,-2,1],[1,-1,0,-1],[-1,0,1,1],[-1,2,1,-1],[1,0,0,0],
...               [-1,0,0,0],[0,0,0,1],[0,0,1,0],[0,1,0,0],[0,1,1,-1]])
>>> cones = p.ntfe_cones()
>>> len(cones)
36
>>> sum(c.is_solid() for c in cones)
30

Source on GitHub

Return (some of) the NTFE FRSTs of the polytope.

This is ntfe_frts with make_star=True; see there for details. See arXiv:2309.10855 for the algorithm.

This function is attached to Polytope as the method ntfe_frsts, where self is the polytope.

Parameters:

• cones (list[Cone] | None, default: None ) –

  The expanded secondary cones to use, e.g. as returned by ntfe_cones. If neither cones nor hypers is specified, the cones are computed.

• hypers (list[ArrayLike] | None, default: None ) –

  The hyperplanes defining the expanded secondary cones to use, e.g. as returned by ntfe_hypers. Takes precedence over cones.

• N (int | None, default: None ) –

  The number of expanded secondary cones (i.e. candidate NTFEs) to sample. If not specified, all of them are used.

• seed (int | None, default: None ) –

  The random seed used when sampling. If not specified, Python's default seeding is used. Note that this reseeds Python's global random module.

• face_ineqs (list[list[csr_matrix]] | None, default: None ) –

  The CPL inequalities of each FRT of each 2-face, as returned by triangface_ineqs. If not specified, they are computed.

• face_triangs (list[list[Triangulation]] | None, default: None ) –

  The FRTs of each 2-face, as returned by face_triangs. Only used if face_ineqs is not specified. If not specified, they are computed.

• max_npts (int, default: 17 ) –

  The maximum number of lattice points of a 2-face for which all FRTs are enumerated (if face_triangs is not specified). For 2-faces with more points, FRTs are only sampled.

• N_face_triangs (int, default: 1000 ) –

  The maximum number of FRTs to sample for each 2-face with more than max_npts points (if face_triangs is not specified).

• triang_method (str, default: 'grow2d' ) –

  The method used to sample FRTs of 2-faces with more than max_npts points (if face_triangs is not specified). The options are "fast", "fair", "grow2d", and "dualgnn"; see face_triangs.

• as_generator (bool, default: False ) –

  Whether to return a generator instead of a list. Use this if memory is a concern.

• n_jobs (int | None, default: None ) –

  The number of parallel workers used to find a height vector in each cone. If not specified, 1 is used (i.e. the computation is sequential); -1 uses all cores.

• heights_only (bool, default: False ) –

  Whether to return the height vectors instead of the triangulations.

• verbosity (int, default: 0 ) –

  The verbosity level.

Returns:

• list | Generator –

  The NTFE FRSTs, as Triangulation objects, or, if heights_only is true, the height vectors realizing them.

Examples:

We find all NTFE FRSTs of a polytope.

>>> from cytools import Polytope
>>> p = Polytope([[1,-1,-2,1],[1,-1,0,-1],[-1,0,1,1],[-1,2,1,-1],[1,0,0,0],
...               [-1,0,0,0],[0,0,0,1],[0,0,1,0],[0,1,0,0],[0,1,1,-1]])
>>> frsts = p.ntfe_frsts()
>>> len(frsts)
30
>>> all(t.is_star() for t in frsts)
True

Source on GitHub

Return (some of) the NTFE FR(S)Ts of the polytope.

For each non-two-face-equivalent (NTFE) class, i.e. each solid expanded secondary cone, a height vector in its strict interior is found with an LP solver and used to construct a fine, regular (star) triangulation. See arXiv:2309.10855 for details.

If none of N, cones, and hypers is specified, all NTFEs are enumerated by a depth-first search over the choices of 2-face FRTs, which prunes partial choices that are already infeasible using an incremental LP. This is much faster than checking every combination of 2-face FRTs, with identical results. Otherwise, the given (or sampled) cones are checked one by one, and the non-solid ones are skipped, so fewer than N triangulations may be returned.

If heights_only is true, no Triangulation objects are constructed and the height vectors realizing each NTFE are returned instead. This is much faster when one only needs to count the NTFEs or post-process the heights.

This function is attached to Polytope as the method ntfe_frts, where self is the polytope.

Parameters:

• cones (list[Cone] | None, default: None ) –

  The expanded secondary cones to use, e.g. as returned by ntfe_cones. If neither cones nor hypers is specified, the cones are computed.

• hypers (list[ArrayLike] | None, default: None ) –

  The hyperplanes defining the expanded secondary cones to use, e.g. as returned by ntfe_hypers. Takes precedence over cones.

• make_star (bool, default: False ) –

  Whether to make the triangulations star, turning the FRTs into FRSTs.

• N (int | None, default: None ) –

  The number of expanded secondary cones (i.e. candidate NTFEs) to sample. If not specified, all of them are used.

• seed (int | None, default: None ) –

  The random seed used when sampling. If not specified, Python's default seeding (from system randomness or the current time) is used. Note that this reseeds Python's global random module. Unused when enumerating all NTFEs.

• face_ineqs (list[list[csr_matrix]] | None, default: None ) –

  The CPL inequalities of each FRT of each 2-face, as returned by triangface_ineqs. If not specified, they are computed.

• face_triangs (list[list[Triangulation]] | None, default: None ) –

  The FRTs of each 2-face, as returned by face_triangs. Only used if face_ineqs is not specified. If not specified, they are computed.

• max_npts (int, default: 17 ) –

  The maximum number of lattice points of a 2-face for which all FRTs are enumerated (if face_triangs is not specified). For 2-faces with more points, FRTs are only sampled.

• N_face_triangs (int, default: 1000 ) –

  The maximum number of FRTs to sample for each 2-face with more than max_npts points (if face_triangs is not specified).

• triang_method (str, default: 'grow2d' ) –

  The method used to sample FRTs of 2-faces with more than max_npts points (if face_triangs is not specified). The options are "fast", "fair", "grow2d", and "dualgnn"; see face_triangs.

• as_generator (bool, default: False ) –

  Whether to return a generator instead of a list. Use this if memory is a concern.

• n_jobs (int | None, default: None ) –

  The number of parallel workers used to find a height vector in each cone. If not specified, 1 is used (i.e. the computation is sequential); -1 uses all cores. This is only worth raising when there are many cones, as each worker pays pickling overhead. Unused when enumerating all NTFEs or when as_generator is true.

• heights_only (bool, default: False ) –

  Whether to return the height vectors instead of the triangulations.

• verbosity (int, default: 0 ) –

  The verbosity level.

Returns:

• list | Generator –

  The NTFE FR(S)Ts, as Triangulation objects, or, if heights_only is true, the height vectors realizing them, as NumPy arrays with one entry per lattice point of the polytope.

Examples:

We find all NTFE FRTs of a polytope. Only 30 of the 36 combinations of 2-face FRTs extend to a triangulation of the polytope.

>>> from cytools import Polytope
>>> p = Polytope([[1,-1,-2,1],[1,-1,0,-1],[-1,0,1,1],[-1,2,1,-1],[1,0,0,0],
...               [-1,0,0,0],[0,0,0,1],[0,0,1,0],[0,1,0,0],[0,1,1,-1]])
>>> frts = p.ntfe_frts()
>>> len(frts)
30
>>> frts[0].is_fine(), frts[0].is_regular(), frts[0].is_star()
(True, True, False)
>>> len(p.ntfe_frts(heights_only=True))
30

Source on GitHub

Return the hyperplanes of (some of) the expanded secondary cones.

Each choice of one FRT per 2-face defines an expanded secondary cone: the intersection of the (lifted) secondary cones of the chosen 2-face FRTs, i.e. the set of height vectors inducing all of them. The choices whose cone is solid are exactly the NTFEs. This function returns the inequalities of these cones, either for all choices or for a random sample of N distinct choices. The cones are not checked for solidity. See arXiv:2309.10855 for details.

This function is attached to Polytope as the method ntfe_hypers, where self is the polytope.

Parameters:

• require_star (bool, default: False ) –

  Whether to also include the inequalities enforcing starness. This is not recommended unless such cones are of direct interest. If one only cares about NTFE FRSTs, it is more efficient to enforce starness when constructing the triangulation, by lowering the height of the origin (i.e. with make_star=True).

• N (int | None, default: None ) –

  The number of distinct choices of 2-face FRTs (i.e. of candidate NTFEs) to sample uniformly at random. If not specified, or if it is at least the total number of choices, all choices are used.

• seed (int | None, default: None ) –

  The random seed used when sampling. If not specified, it is derived from the current time. NumPy's global random state is not affected.

• face_ineqs (list[list[csr_matrix]] | None, default: None ) –

  The CPL inequalities of each FRT of each 2-face, as returned by triangface_ineqs. If not specified, they are computed.

• face_triangs (list[list[Triangulation]] | None, default: None ) –

  The FRTs of each 2-face, as returned by face_triangs. Only used if face_ineqs is not specified. If not specified, they are computed.

• max_npts (int, default: 17 ) –

  The maximum number of lattice points of a 2-face for which all FRTs are enumerated (if face_triangs is not specified). For 2-faces with more points, FRTs are only sampled.

• N_face_triangs (int, default: 1000 ) –

  The maximum number of FRTs to sample for each 2-face with more than max_npts points (if face_triangs is not specified).

• triang_method (str, default: 'grow2d' ) –

  The method used to sample FRTs of 2-faces with more than max_npts points (if face_triangs is not specified). The options are "fast", "fair", "grow2d", and "dualgnn"; see face_triangs.

• as_generator (bool, default: False ) –

  Whether to return a generator instead of a list. Use this if memory is a concern.

• separate_boring (bool, default: True ) –

  Whether to merge the inequalities of all 2-faces with a single FRT into one block. This only changes the internal ordering of the 2-faces, and hence the order of the outputs and which cones are picked when sampling.

• verbosity (int, default: 0 ) –

  The verbosity level.

Returns:

• list[CSR_stack] | Generator[CSR_stack, None, None] –

  The hyperplanes of each expanded secondary cone, as CSR_stack objects (from cytools.helpers.matrix) with one inward-facing normal per row and one column per lattice point of the polytope.

Examples:

We compute the hyperplanes of the expanded secondary cones of a polytope whose 2-faces have 36 combinations of FRTs.

>>> from cytools import Polytope
>>> p = Polytope([[1,-1,-2,1],[1,-1,0,-1],[-1,0,1,1],[-1,2,1,-1],[1,0,0,0],
...               [-1,0,0,0],[0,0,0,1],[0,0,1,0],[0,1,0,0],[0,1,1,-1]])
>>> hypers = p.ntfe_hypers()
>>> len(hypers)
36
>>> hypers[0]
CSR_stack(shape=(11, 13))

Source on GitHub

Compute the FRTs of the 2-faces and their CPL inequalities.

For each FRT of each 2-face, this computes the inequalities cutting out its secondary cone, lifted to the space of height vectors of the polytope (one entry per lattice point, indexed by point label). These are the building blocks of the expanded secondary cones (see ntfe_hypers).

This function is attached to Polytope as the method triangface_ineqs, where self is the polytope.

Parameters:

• face_triangs (list[list[Triangulation]] | None, default: None ) –

  The FRTs of each 2-face, as returned by face_triangs. If not specified, they are computed.

• require_star (bool, default: False ) –

  Whether to also include the inequalities enforcing starness. This is not recommended unless such cones are of direct interest. If one only cares about NTFE FRSTs, it is more efficient to enforce starness when constructing the triangulation, by lowering the height of the origin (i.e. with make_star=True).

• max_npts (int, default: 17 ) –

  The maximum number of lattice points of a 2-face for which all FRTs are enumerated (if face_triangs is not specified). For 2-faces with more points, FRTs are only sampled.

• N_face_triangs (int, default: 1000 ) –

  The maximum number of FRTs to sample for each 2-face with more than max_npts points (if face_triangs is not specified).

• triang_method (str, default: 'grow2d' ) –

  The method used to sample FRTs of 2-faces with more than max_npts points (if face_triangs is not specified). The options are "fast", "fair", "grow2d", and "dualgnn"; see face_triangs.

• return_triangs (bool, default: False ) –

  Whether to also return the 2-face triangulations.

• verbosity (int, default: 0 ) –

  The verbosity level.

Returns:

• list | tuple –

  For each 2-face (in the order of self.faces(2)), a list with the inequalities of each of its FRTs, each as a sparse matrix with one inward-facing normal per row. If return_triangs is true, a tuple of this list and the 2-face triangulations is returned instead.

Examples:

>>> from cytools import Polytope
>>> p = Polytope([[1,-1,-2,1],[1,-1,0,-1],[-1,0,1,1],[-1,2,1,-1],[1,0,0,0],
...               [-1,0,0,0],[0,0,0,1],[0,0,1,0],[0,1,0,0],[0,1,1,-1]])
>>> ineqs = p.triangface_ineqs()
>>> [len(f) for f in ineqs]  # number of FRTs of each 2-face
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 2, 2, 1, 1]

Source on GitHub

Construct an FRST that restricts to the given 2-face triangulations.

This is triangfaces_to_frt with make_star=True. Some 2-faces can be left free by setting the corresponding entries of triangs to None, or by omitting them. See arXiv:2309.10855 for details.

This function is attached to Polytope as the method triangfaces_to_frst, where self is the polytope.

Parameters:

• triangs (list[Triangulation | None]) –

  The 2-face triangulations, with points labelled as in the polytope (e.g. as returned by face_triangs). None entries leave the corresponding 2-face free.

• check_heights (bool, default: False ) –

  Whether to check that the heights uniquely define the triangulation (see check_heights).

• verbosity (int, default: 0 ) –

  The verbosity level. Currently unused.

Returns:

• Triangulation | None –

  An FRST that restricts to the specified 2-face triangulations, or None if no such triangulation was found.

Examples:

We construct an FRST that restricts to the first FRT of each 2-face.

>>> from cytools import Polytope
>>> p = Polytope([[1,-1,-2,1],[1,-1,0,-1],[-1,0,1,1],[-1,2,1,-1],[1,0,0,0],
...               [-1,0,0,0],[0,0,0,1],[0,0,1,0],[0,1,0,0],[0,1,1,-1]])
>>> triangs = [ft[0] for ft in p.face_triangs()]
>>> t = p.triangfaces_to_frst(triangs)
>>> t.is_fine(), t.is_regular(), t.is_star()
(True, True, True)

Source on GitHub

Construct an FR(S)T that restricts to the given 2-face triangulations.

A height vector in the strict interior of the cone given by cone_of_permissible_heights is found, and the polytope is triangulated with it (without points interior to facets). Some 2-faces can be left free by setting the corresponding entries of triangs to None, or by omitting them. See arXiv:2309.10855 for details.

This function is attached to Polytope as the method triangfaces_to_frt, where self is the polytope.

Parameters:

• triangs (list[Triangulation | None]) –

  The 2-face triangulations, with points labelled as in the polytope (e.g. as returned by face_triangs). None entries leave the corresponding 2-face free.

• make_star (bool, default: False ) –

  Whether to make the triangulation star, turning the FRT into an FRST.

• check_heights (bool, default: False ) –

  Whether to check that the heights uniquely define the triangulation (see check_heights).

• verbosity (int, default: 0 ) –

  The verbosity level. Currently unused.

Returns:

• Triangulation | None –

  An FR(S)T that restricts to the specified 2-face triangulations, or None if no such triangulation was found (i.e. if the cone of permissible heights is not solid).

Examples:

We construct an FRT that restricts to the first FRT of each 2-face.

>>> from cytools import Polytope
>>> p = Polytope([[1,-1,-2,1],[1,-1,0,-1],[-1,0,1,1],[-1,2,1,-1],[1,0,0,0],
...               [-1,0,0,0],[0,0,0,1],[0,0,1,0],[0,1,0,0],[0,1,1,-1]])
>>> triangs = [ft[0] for ft in p.face_triangs()]
>>> t = p.triangfaces_to_frt(triangs)
>>> t.is_fine(), t.is_regular(), t.is_star()
(True, True, False)

Source on GitHub

Return the fine triangulations of each dim-dimensional face.

For each dim-face of the polytope, all of its fine triangulations are enumerated with TOPCOM (see Polytope.all_triangulations). If max_npts is specified, faces with more than max_npts lattice points are instead sampled: up to N_face_triangs fine, regular triangulations are generated with the method given by triang_method. All lattice points of each face are used, and the triangulations are never made star.

This function is attached to Polytope as the method face_triangs, where self is the polytope.

Parameters:

• dim (int, default: 2 ) –

  The dimension of the faces to triangulate. The "grow2d" and "dualgnn" sampling methods only work for 2-faces.

• which (int | list[int] | None, default: None ) –

  The index, or list of indices, of the faces to triangulate, as positions in self.faces(dim). If not specified, all dim-faces are triangulated.

• only_regular (bool, default: True ) –

  Whether to only enumerate regular triangulations. This only affects faces that are fully enumerated; sampled triangulations are always regular.

• max_npts (int | None, default: None ) –

  The maximum number of lattice points of a face for which all triangulations are enumerated. Faces with more points are sampled instead. If not specified, all triangulations of every face are enumerated.

• N_face_triangs (int, default: 1000 ) –

  The maximum number of triangulations to sample for each face with more than max_npts points. Fewer may be returned.

• triang_method (str, default: 'grow2d' ) –

  The method used to sample triangulations of faces with more than max_npts points. The options are "fast" and "fair" (which use the fast and fair random triangulation samplers of Polytope), "grow2d" (see grow_frt), and "dualgnn", which samples FRTs with a graph neural network (arXiv:2605.27770) and requires the optional dualgnn package.

• dualgnn_model (DualGNN | str | None, default: None ) –

  Only used if triang_method="dualgnn". A dualgnn.model.DualGNN instance, or a path to a model checkpoint. If not specified, the default checkpoint shipped with the dualgnn package is used.

• seed (int | None, default: None ) –

  The random seed used when sampling triangulations.

• verbosity (int, default: 0 ) –

  The verbosity level.

Returns:

• list[list[Triangulation]] –

  One list of triangulations per face, in the same order as self.faces(dim) (or as which, if specified).

Raises:

• ValueError –

  If triang_method is not one of the allowed options.

Examples:

We find the fine, regular triangulations of each 2-face of a polytope and count them. Most of its 2-faces have a unique FRT.

>>> from cytools import Polytope
>>> p = Polytope([[1,-1,-2,1],[1,-1,0,-1],[-1,0,1,1],[-1,2,1,-1],[1,0,0,0],
...               [-1,0,0,0],[0,0,0,1],[0,0,1,0],[0,1,0,0],[0,1,1,-1]])
>>> ft = p.face_triangs()
>>> [len(f) for f in ft]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 2, 2, 1, 1]
>>> ft[19][0].simplices()  # one of the FRTs of a 2-face with 3 FRTs
array([[ 3,  7,  9],
       [ 3,  9, 12],
       [ 4,  9, 12]], dtype=uint8)

Source on GitHub

Randomly grow fine, regular triangulations (FRTs) of a polygon.

Fine triangulations are repeatedly grown with grow_ft (incrementing the seed after each attempt), and the regular ones are kept, until N distinct FRTs are found or max_N_tries attempts have been made.

This function is attached to Polytope as the method grow_frt, where self is the polygon.

Parameters:

• N (int, default: 1 ) –

  The number of distinct FRTs to grow.

• max_N_tries (int | None, default: None ) –

  The maximum number of growth attempts. If not specified, 100*N is used.

• bdry (Iterable[Iterable[int]] | None, default: None ) –

  The boundary edges of the polygon, each given as an iterable of the labels of its two endpoints (as returned by Polytope.get_bdry). If not specified, they are computed once and reused across attempts.

• seed (int | None, default: None ) –

  The seed for the random number generator. If not specified, it is derived from the current time.

• backend (str | None, default: None ) –

  The backend used to check regularity. See is_regular.

• verbosity (int, default: 0 ) –

  The verbosity level.

Returns:

• Triangulation | set[Triangulation] –

  If exactly one distinct FRT was found, that triangulation. Otherwise, the set of FRTs that were found, which contains at most N elements and may be empty.

Raises:

• NotImplementedError –

  If the polytope is not 2-dimensional.

Examples:

We grow three distinct FRTs of one of the 2-faces of a polytope.

>>> from cytools import Polytope
>>> p = Polytope([[1,-1,-2,1],[1,-1,0,-1],[-1,0,1,1],[-1,2,1,-1],[1,0,0,0],
...               [-1,0,0,0],[0,0,0,1],[0,0,1,0],[0,1,0,0],[0,1,1,-1]])
>>> f = p.faces(2)[19].as_poly()
>>> frts = f.grow_frt(N=3, seed=0)
>>> len(frts)
3

Source on GitHub

Randomly grow a fine triangulation (FT) of a polygon.

Starting from a random unimodular triangle (one with no lattice points other than its vertices), unimodular triangles are repeatedly glued onto random non-boundary edges until no such edges are left. Since every triangle is unimodular, the result is fine. It need not be regular; see grow_frt for that.

If the polytope does not live in a 2D ambient lattice, the triangulation is built on an equivalent polytope in \(\mathbb{Z}^2\) with the same point labels.

This function is attached to Polytope as the method grow_ft, where self is the polygon.

Parameters:

• bdry (Iterable[Iterable[int]] | None, default: None ) –

  The boundary edges of the polygon, each given as an iterable of the labels of its two endpoints (as returned by Polytope.get_bdry). If not specified, they are computed.

• seed (int | None, default: None ) –

  The seed for the random number generator. If not specified, it is derived from the current time.

• verbosity (int, default: 0 ) –

  The verbosity level.

Returns:

• Triangulation | None –

  The fine triangulation, or None (with a warning) if the growth got stuck.

Raises:

• NotImplementedError –

  If the polytope is not 2-dimensional.

Examples:

We grow a fine triangulation of one of the 2-faces of a polytope.

>>> from cytools import Polytope
>>> p = Polytope([[1,-1,-2,1],[1,-1,0,-1],[-1,0,1,1],[-1,2,1,-1],[1,0,0,0],
...               [-1,0,0,0],[0,0,0,1],[0,0,1,0],[0,1,0,0],[0,1,1,-1]])
>>> f = p.faces(2)[19].as_poly()
>>> t = f.grow_ft(seed=0)
>>> t.simplices()
array([[ 3,  7, 12],
       [ 4,  9, 12],
       [ 7,  9, 12]], dtype=uint8)
>>> t.is_fine()
True

Source on GitHub

Return the number of combinations of fine 2-face triangulations.

This is the product, over the 2-faces of the polytope, of the number of fine triangulations of each 2-face. It is an upper bound on the number of NTFEs, since not every combination extends to a triangulation of the full polytope (see ntfe_frts). All triangulations of every 2-face are enumerated, which can be slow for large 2-faces.

This function is attached to Polytope as the methods n_2face_triangs and num_2face_triangs, where self is the polytope.

Parameters:

• only_regular (bool, default: True ) –

  Whether to only count regular 2-face triangulations.

Returns:

• int –

  The number of combinations of fine 2-face triangulations.

Examples:

>>> from cytools import Polytope
>>> p = Polytope([[1,-1,-2,1],[1,-1,0,-1],[-1,0,1,1],[-1,2,1,-1],[1,0,0,0],
...               [-1,0,0,0],[0,0,0,1],[0,0,1,0],[0,1,0,0],[0,1,1,-1]])
>>> p.n_2face_triangs()
36

Source on GitHub