key: cord-0047189-71bf4w44
authors: Betten, Anton; Mukthineni, Tarun
title: Classifying Simplicial Dissections of Convex Polyhedra with Symmetry
date: 2020-06-06
journal: Mathematical Software - ICMS 2020
DOI: 10.1007/978-3-030-52200-1_14
sha: 269a5e6f3c8a46d3ef96ffc2eede944f372bfac6
doc_id: 47189
cord_uid: 71bf4w44

A convex polyhedron is the convex hull of a finite set of points in [Formula: see text] A triangulation of a convex polyhedron is a decomposition into a finite number of 3-simplices such that any two intersect in a common face or are disjoint. A simplicial dissection is a decomposition into a finite number of 3-simplices such that no two share an interior point. We present an algorithm to classify the simplicial dissections of a regular polyhedron under the symmetry group of the prolyhedron.

A convex polyhedron is the convex hull of a finite set of points in R 3 . A triangulation of a convex polyhedron is a decomposition into a finite number of 3-simplices such that any two intersect in a common face or are disjoint. A simplicial dissection is a decomposition into a finite number of 3-simplices such that no two share an interior point. A simplicial dissection is a triangulation but not conversely. The problem is that the intersection of two simplices in a dissection may not be face.

Standard implementations for enumerating triangulations include TOPCOM and mptopcom [10] (neither one can enumerate dissections, though). A parallel algorithm to classify regular triangulations with applications in tropical geometry is described in [6] . Regarding the enumeration of all triangulations, see [4] . For minimal dissections, see [1] .

The goal of this paper is to present an efficient algorithm to classify the simplicial dissections of a regular polyhedron under the symmetry group (or automorphism group) G of the polyhedron P. Two dissections of P are equivalent is there is a symmetry g ∈ G which maps one to the other. The classification algorithm utilizes the concept of a partially ordered set under a group action, using the theory developed by Plesken [9] as a framework. The partially ordered set is the search space, which is to be partitioned into orbits. The ranking of the poset introduces level sets, and the orbits partition these level sets. The efficiency of the orbit algorithm is based on an effective use of isomorph rejection. This is the problem of deciding when two objects belong to the same G-orbit. Isomorph rejection is necessary to avoid duplicates, and it helps reduce the number of objects in the search space that have to be examined. The ultimate goal of the classification algorithm is to establish the poset of orbits of G. Isomorphism testing is expensive, and the algorithm that we propose avoids backtracking at the cost of memory. Such trade-off between time complexity and space complexity is common in algorithm design, and it has proved to be useful for other classification problems before. The first author has previously used this technique to classify objects like cubic surfaces, packings in projective space and other objects.

In this note, we will develop an efficient algorithm to classify the simplicial dissections of a polyhedra. As an application, we compute and classify the simplicial dissections of the cube. We use the binary representation of the integers from 0 to 7 to denote the vertices of the cube (cf. Figure 1) , with two vertices adjacent if their Hamming distance is one. The Hamming distance is the number of components which differ in the binary expansion. The automorphism group of the cube has order 48 and is generated by the three permutations (0, 1, 3, 2)(4, 5, 7, 6), (0, 1, 5, 4)(2, 3, 7, 6), (0, 1)(2, 3)(4, 5)(6, 7).

The tetrahedra are encoded using the lexicographic rank of their vertex set among the set of 4-subsets of {0, . . . , 7}: Theorem 1. The number of equivalence classes of simplicial dissections of the cube under its automorphism group of order 48 is exactly 10. Six of these are triangulations as described in [5] . A system of representatives is given in Table 1 , together with the order of the automorphism group. A more detailed drawing of the representatives is shown in Table 2 . A tretrahedron is spatial if it has positive volume. Out of the list of 70 tetrahedra, 12 are flat. The remaining 58 are spatial and can be used for triangulating the cube. Following Takeuchi and Imai [12] , triangulations can be identified using large cliques in a certain graph Γ , which we call the disjointness graph. This terminology is somewhat abusive, since the graph measures if the interior point sets of the tetrahedra are disjoint: Boundary points may or may not intersect. The vertices of Γ are the spatial tetrahedra. Two vertices are adjacent if the associated tetrahedra are non-overlapping, i.e. they do not share an interior point. The adjacency matrix of Γ is shown in Table 2 . 

As pointed out by De Loera et al. [5] , there are four types of tetrahedra under the action of the group. The four types are listed in Table 3 .

The table lists the volume of each tetrahedron, based on a cube of side length one. The type vector of a triangulation is the vector (a, b, c, d) where a is the number of Cores, b is the number of Corners, c is the number of Staircases, and d is the number of Slanted pieces. The Corner, Staircase and Slanted pieces each have volume 1 6 , whereas the Core piece has volume 1 3 . From this it follows that a triangulation or dissection either has 5 tetrahedra and includes a Core piece, or it has 6 tetrahedra, none of which are Core. This means that the type vector satisfies In Table 4 , the list of dissections from Theorem 1 is listed, with tetrahedra separated out by type. The type vector is listed in the column headed type. For triangulations, the De Loera number is in the column headed DL. This will be discussed in Sect. 4.

Poset classification is a technique to classify combinatorial objects. Canonical augmentation due to McKay [7] is a very popular technique. McKay introduces the idea of a canonical predecessor to achieve the isomorph classification.

McKay's work relies on the notion of a canonical form. His computer package Nauty [8] can compute canonical forms for graphs efficiently. This has led many authors to reduce the classification of different types of combinatorial structures to that of graphs. The original combinatorial objects are equivalent if and only if the associated graphs are isomorphic. By using Nauty to solve the isomorphism problem for the associated graphs, the combinatorial objects at hand are classified as well. For many combinatorial objects, this reduction is efficient and works very well. However, there are combinatorial objects for which this reduction is inefficient. Also, there is an interest in solving the isomorphism problem for the original combinatorial objects at hand directly, and avoiding the reduction to graphs altogether. A second approach to classify combinatorial objects is losely based on ideas of Schmalz [11] for the enumeration of double cosets in groups. This has been adapted to the problem of classifying the orbits of groups on various posets. The critical operation in any poset orbit classification algorithm is the isomorphism testing. Using the ideas of Schmalz, backtracking can be avoided at the expense of higher memory complexity. The poset is examined breadth-first, using the rank of the combinatorial objects at hand. For most combinatorial objects, such rank functions are implicit. For instance, for orbits on sets, the size of the set is the rank of the set. In order to do isomorphism test in linear time, previously computed data in lower levels of the poset is utilized when constructing the next level in the poset. For a recent description of this technique, including some comparisons with canonical augmentation, see [3] .

Let (P, ≺) be a partially ordered set with rank function. Assume that G is a group that acts on P (with the action written on the right). This means that for all g ∈ G and all a, b ∈ P we have

Let P i be the set of objects at level i in P. The poset of orbits for the action of G on P has as elements the orbits of G. Two orbits O 1 and O 2 are related with there exists a ∈ O 1 and b ∈ O 2 with a ≺ b.

For computing dissections of a polyhedron P with automorphism group G, let P be the set of partial dissections. A partial dissection is a set of spacial tetrahedra (simplices) which do not intersect in an interior point. The poset P is ordered with respect to inclusion. The group G of the polyhedron acts on this poset. The rank of a dissection is the number of simpices in it. The level set P i contains all partial dissection size i. The dissections of the cube can be recognized using the volume function from Table 3 . Dissections containing a Core tetrahedra have rank 5. All other dissections have rank 6. As all partial dissections correspond to cliques in the disjointness graph Γ of Table 2 , the problem of finding dissections is reduced to that of finding suitable cliques in the graph Γ.

Let us present some results from the classification, computed using Orbiter [2] . The number of orbits of G on each of the levels P i for i = 0, . . . , 6 is shown in Table 5 . The poset of orbits for the action of the group of the cube on the partial dissections is shown in Fig. 3 .

The labeling of the representatives of the dissections is as in Table 1 .

De Loera, Rambau and Santos [5] list six types of triangulations of the cube. In Table 6 , the De Loera triangulations are listed and identified with orbits in Table 4 . An isomorphism from the representative picked by De Loera to the representative in Table 4 is given. 

Minimal simplicial dissections and triangulations of convex 3-polytopes

Orbiter -a program to classify discrete objects

How fast can we compute orbits of groups?

The polytope of all triangulations of a point configuration

Triangulations. Structures for Algorithms and Applications

Parallel enumeration of triangulations. Electron

Isomorph-free exhaustive generation

Nauty User's Guide (Version 2.6)

Counting with groups and rings

TOPCOM: triangulations of point configurations and oriented matroids

Verwendung von Untergruppenleitern zur Bestimmung von Doppelnebenklassen

Enumerating triangulations for products of two simplices and for arbitrary configurations of points

The authors thank the three referees for helpful comments which have increased the clarity of the exposition.