Extremal Properties for Dissections of Convex 3-Polytopes.
A dissection of a convex d-polytope is a partition of the polytope into d-simplices whose vertices are among the vertices of the polytope. Triangulations are dissections that have the additional property that the set of all its simplices forms a simplicial complex. The size of a dissection is the number of d-simplices it contains. This paper compares triangulations of maximal size with dissections of maximal size. We also exhibit lower and upper bounds for the size of dissections of a 3-polytope and analyze extremal size triangulations for specific nonsimplicial polytopes: prisms, antiprisms, Archimedean solids, and combinatorial d-cubes.
Introduction
. Let A be a point conguration in R d with its convex hull
having dimension d. A set of d-simplices with vertices in A is a dissection
of A if no pair of simplices has an interior point in common and their union equals
conv(A). A dissection is a triangulation of A if in addition any pair of simplices
intersects at a common face (possibly empty). The size of a dissection is the number
of d-simplices it contains. We say that a dissection is mismatching when it is not a
triangulation (i.e. it is not a simplicial complex). In this paper we study mismatching
dissections of maximal possible size for a convex polytope and compare them with
maximal triangulations. This investigation is related to the study of Hilbert bases
and the hierarchy of covering properties for polyhedral cones which is relevant in
Algebraic Geometry and Integer Programming (see [5, 10, 24]). Maximal dissections
are relevant also in the enumeration of interior lattice points and its applications (see
[2, 15] and references there).
It was rst shown by Lagarias and Ziegler that dissections of maximal size turn
out to be, in general, larger than maximal triangulations, but their example uses
interior points [16]. Similar investigations were undertaken for mismatching minimal
dissections and minimal triangulations of convex polytopes [4]. In this paper we
augment previous results by showing that it is possible to have simultaneously, in
the same 3-polytope, that the size of a mismatching minimal (maximal) dissection
is smaller (larger) than any minimal (maximal) triangulation. In addition, we show
that the gap between the size of a mismatching maximal dissection and a maximal
triangulation can grow linearly on the number of vertices and that this occurs already
for a family of simplicial convex 3-polytopes. A natural question is how dierent
are the upper and lower bounds for the size of mismatching dissections versus those
bounds known for triangulations (see [21]). We prove lower and upper bounds on their
size with respect to the number of vertices for dimension three and exhibit examples
showing that our technique of proof fails already in dimension four. Here is the rst
Dept. of Mathematics, Univ. of California-Davis (deloera@math.ucdavis.edu). The research of
this author partially supported by NSF grant DMS-0073815.
y Depto. de Matematicas, Estad. y Comput., Univ. de Cantabria (santos@matesco.unican.es).
The research of this author was supported partially by grant PB97-0358 of the Spanish Direccion
General de Investigacion Cientca y Tecnica.
z Dept. of Information Science, Univ. of Tokyo (fumi@is.s.u-tokyo.ac.jp).
summary of results:
Theorem 1.1.
1. There exists an innite family of convex simplicial 3-polytopes with increasing
number of vertices whose mismatching maximal dissections are larger than
their maximal triangulations. This gap is linear in the number of vertices
(Corollary 2.2).
2. (a) There exists a lattice 3-polytope with 8 vertices containing no other lattice
point other than its vertices whose maximal dissection is larger than its
maximal triangulations.
(b) There exists a 3-polytope with 8 vertices for which, simultaneously, its
minimal dissection is smaller than minimal triangulations and maximal
dissection is larger than maximal triangulations.
(Proposition 2.3)
3. If D is a mismatching dissection of a 3-polytope with n vertices, then the size
of D is at least n 2. In addition, the size of D is bounded above by n 2
(Proposition 3.2).
A consequence of our third point is that the result of [4], stating a linear gap
between the size of minimal dissections and minimal triangulations, is best possible.
The results are discussed in Sections 2 and 3.
The last section presents a study of maximal and minimal triangulations for
combinatorial d-cubes, three-dimensional prisms and anti-prisms, as well as other
Archimedean polytopes. The following theorem and table summarize the main results:
Theorem 1.2.
1. There is a constant c > 1 such that for every d  3 the maximal triangulation
among all possible combinatorial d-cubes has size at least c d d! (Proposition
4.1).
2. For a three-dimensional m-prism, in any of its possible coordinatizations, the
size of a minimal triangulation is 2m 5+ d me. For an m-antiprism, in any
of its possible coordinatizations, the size of a minimal triangulation is 3m 5
(Proposition 4.3). The size of a maximal triangulation of an m-prism depends
on the coordinatization, and in certain natural cases it is (m
(Proposition 4.4).
3. The following table species sizes of the minimal and maximal triangulations
for some Platonic and Archimidean solids. These results were obtained via
integer programming calculations using the approach described in [8]. All computations
used the canonical symmetric coordinatizations for these polytopes
[6]. The number of vertices is indicated in parenthesis (Remark 4.5):
Icosahedron (12) 15 20
Dodecahedron (20) 23 36
Cuboctahedron
Icosidodecahedron
Truncated
Truncated Octahedron
Truncated Cube (24) 25 48
Small Rhombicuboctahedron
Pentakis Dodecahedron (32) 54 ?
Rhombododecahedron

Table
Sizes of extremal triangulations of Platonic and Archimidean solids.
2. Maximal dissections of 3-polytopes. We introduce some important de-
nitions and conventions: We denote by Qm a convex m-gon with m an even positive
be two edges parallel to Qm , orthogonal to each other,
on opposite sides of the plane containing Qm , and such that the four segments v i
intersect the interior of Qm . We suppose that v 1 v 2 and u 1 u 2 are not parallel to any
diagonal or edge of Qm . The convex hull Pm of these points has m+ 4 vertices and it
is a simplicial polytope. We will call north (respectively south) vertex of Qm the one
which maximizes (respectively minimizes) the scalar product with the vector v 2 v 1 .
Similarly, we will call east (west) the vertex which maximizes (minimizes) the scalar
product with u 2 u 1 . We denote these four vertices n, s, e and w, respectively. See

Figure

2.1.
e
s
Fig. 2.1. North, South, East, and West vertices.
We say that a directed path of edges inside Qm is monotone in the direction v 1
(respectively when the vertices of the path appear in the path following the same
order given by the scalar product with
formulation is that any line orthogonal to v 1 v 2 cuts the path in at most one point.
We remark that by our choice of v 1 v 2 and u 1 u 2 all vertices of Qm are ordered by the
values of their scalar products with v 2 v 1 and also with respect to u 2 u 1 . In the
same way, a sequence of vertices of Qm is ordered in the direction of v 1 v 2 (respectively
if the order is the same as the one provided by using the values of the scalar
products of the points with the vector Consider the
two orderings induced by the directions of v 1 v 2 and u 1 u 2 on the set of vertices of Qm .
Let us call horizontal (respectively vertical) any edge joining two consecutive vertices
in the direction of v 1 v 2 (respectively of u 1 u 2 ). As an example, if Qm is regular then
the vertical edges in Qm form a zig-zag path as shown in Figure 2.2.
Our examples in this section will be based on the following observation and are
inspired by a similar analysis of maximal dissections of dilated empty lattice tetrahedra
in R 3 by Lagarias and Ziegler [16]: Let Rm be the convex hull of the m+2 vertices
consisting of the m-gon Qm and . Rm is exactly one half of the polytope Pm .
Consider a triangulation T 0 of Qm and a path of edges of T 0 monotone with respect
to the direction u 1 u 2 . Observe that divides T 0 in two regions, which we will call
the \north" and the \south". Then, the following three families of tetrahedra form a
triangulation T of Rm : the edges of joined to the edge the southern triangles
of T 0 joined to v 1 ; and the northern triangles of T 0 joined to v 2 (see Figure 2.3).
Moreover, all the triangulations of Rm are obtained in this way: Any triangulation T
e
Fig. 2.2. The minimal monotone path (middle) and the maximal monotone path made by the
vertical edges (right) in the direction u 1 u 2 .
s
e
s
e
s
e
Fig. 2.3. Three types of tetrahedra in Rm .
of Rm induces a triangulation T 0 of Qm . The link of v 1 v 2 in T is a monotone path of
edges contained in T 0 and it divides T 0 in two regions, joined respectively to v 1 and
Using the Cayley trick, one can also think of the triangulations of Rm as the ne
mixed subdivisions of the Minkowski sum Qm (see [13] and references within).
The size of a triangulation of Rm equals is the number of
edges in the path . There is a unique minimal path in Qm of length one (Figure
2.2, middle) and a unique maximal path of length m 1 (Figure 2.2, right). Hence
the minimal and maximal triangulations of Rm have, respectively, m 1 and 2m 3
tetrahedra. The maximal triangulation is unique, but the minimal one is not: after
choosing the diagonal in the rest of the polygon Qm can be triangulated in many
ways. From the above discussion regarding Rm we see that we could independently
triangulate each of the two halves of Pm with any number of tetrahedra from m 1
to 2m 3. Hence, Pm has dissections of sizes going from 2m 2 to 4m 6. Among
the triangulations of Pm , we will call halving triangulations those that triangulate the
two halves of Pm . Equivalently, the halving triangulations are those which do not
contain any of the four edges
Proposition 2.1. Let Pm be as described above, with Qm being a regular m-gon.
No triangulation of Pm has more than 7m+ 1 tetrahedra. On the other hand, there
are mismatching dissections of Pm with 4m 6 tetrahedra.
Proof. Let T be a triangulation of Pm . It is an easy application of Euler's formulas
for the 3-ball and 2-sphere that the number of tetrahedra in a triangulation of any
3-ball without interior vertices equals the number of vertices plus interior edges minus
three (such formula appears for instance in [9]). Hence our task is to prove that T has
at most 5minterior edges. For this, we classify the interior edges according to how
many vertices of Qm they are incident to. There are only four edges not incident to
any vertex of Qm (the edges contains at most m 3
edges incident to two vertices of Qm (i.e. diagonals of Qm ), since in any family of
more than m 3 such edges there are pairs which cross each other. Thus, it su-ces
to prove that T contains at most 3m1 edges incident to just one vertex of Qm , i.e.
of the form v i p or u i p with
Let p be any vertex of Qm . If p equals w or e then the edges pv 1 and pv 2 are both
in the boundary of Pm ; for any other p, exactly one of pv 1 and pv 2 is on the boundary
and the other one is interior. Moreover, we claim that if pv i is an interior edge in a
triangulation T , then the triangle pv 1 v 2 appears in T . This is so because there is a
plane containing pv i and having v 3 i as the unique vertex on one side. At the same
time the link of pv i is a cycle going around the edge. Hence, v 3 i must appear in the
link of pv i . It follows from the above claim that the number of interior edges of the
form pv i in T equals the number of vertices of Qm other than w and e in the link of
In a similar way, the number of interior edges of the form pu i in T equals the
number of vertices of Qm other than n and s in the link of u 1 u 2 . In other words, if
we call in the index
and of the vertices are reversed, because in this way u is monotone with respect to
with respect to v 1 v 2 ), then the number of interior edges in T incident
to exactly one vertex of Qm equals jvertices( v )j Our goal is to
bound this number. As an example, Figure 2.4 shows the intersection of Qm with a
certain triangulation of Pm 12). The link of v 1 v 2 in this triangulation is the
chain of vertices and edges wabu 1 nu 2 ce (the star of v 1 v 2 is marked in thick and grey
in the gure). u consists of the chains wab and ce and the isolated vertex n. In turn,
the link of u 1 u 2 is the chain nv 1 s and v consists of the isolated vertices n and s.
s
e
a
c
Fig. 2.4. Illustration of the proof of Proposition 2.1.
Observe that v has at most three connected components, because it is obtained
by removing from link T the parts of it incident to v 1 and v 2 , if any.
Each component is monotone in the direction of v 1 v 2 and the projections of any two
components to a line parallel to v 1 v 2 do not overlap. The sequence of vertices of Qm
ordered in the direction of v 1 v 2 , can have a pair of consecutive vertices contained in
only where there is a horizontal edge in v or in the at most two discontinuities
of v . This is true because Qm is a regular m-gon.
We denote n hor the number of horizontal edges in v and n 0
hor this number plus
the number of discontinuities in v (hence n 0
hor  n hor non-horizontal
edge of v produces a jump of at least two in the v 1 v 2 -ordering of the vertices of Pm ,
hence we have
hor
hor
Analogously, and with the obvious similar meaning for n vert and n 0
vert ,
jvertices(
vert
vert
can be completed to a triangulation of Qm , and exactly four non-
interior edges of Qm are horizontal or vertical, we have n hor
hor
vert  m+ 5. Hence,
hor
vert
3:
Thus, there are at most 3m1 interior edges in T of the form pv i or pu i and at
most 5minterior edges in total, as desired.
Corollary 2.2. The polytope Pm described above has the following properties:
It is a simplicial 3-polytope with m+ 4 vertices.
Its maximal dissection has at least 4m 6 tetrahedra.
Its maximal triangulation has at most 7m+ 1 tetrahedra.
In particular, the gap between sizes of the maximal dissection and maximal triangulation
is linear on the number of vertices.
Three remarks are in order: First, the size of the maximal triangulation for Pm
may depend on the coordinates or, more specically on which diagonals of Qm intersect
the tetrahedron v 1 concerning the size of the minimal triangulation
of Pm , we can easily describe a triangulation of Pm with only m+ 5 tetrahedra:
let the vertices n, s, e and w be as dened above (see Figure 2.1) and let us call
northeast, northwest, southeast and southwest the edges in the arcs ne, nw, se and
sw in the boundary of Qm . Then, the triangulation consists of the ve tetrahedra
(shown in the left part of Figure
2.5) together with the edges respectively, to the
northeast, northwest, southeast and southwest edges of Qm . The right part of Figure
2.5 shows the result of slicing through the triangulation by the plane containing the
polygon Qm .
Finally, although the corollary above states a dierence between maximal dissections
and maximal triangulations only for Pm with m > 14, experimentally we have
observed there is a gap already for 8. Now we discuss two other interesting
examples. The following proposition constitutes the proof of Theorem 1.1 (2).
Proposition 2.3.
1. Consider the following eight points in R 3
The vertices of
a square in the plane
The vertices of a horizontal edge above
the square, and
The vertices of a horizontal edge
below the square.
These eight points are the vertices of a polytope P whose only integer points
are precisely its eight vertices and with the following properties:
(a) Its (unique) maximal dissection has 12 tetrahedra. All of them are uni-
modular, i.e. they have volume 1=6.
(b) Its (several) maximal triangulations have 11 tetrahedra.
e
s
e
s
Fig. 2.5. For the triangulation of Pm with its ve central tetrahedra (left)
and the intersection of the triangulation with the polygon Qm (right) are shown. The four interior
vertices are the intersection points of the edges with the plane containing
Qm .
2. For the 3-polytope with vertices
the sizes of its (unique) minimal dissection and (several) minimal triangulations
are 6 and 7 respectively, and the sizes of its (several) maximal triangulations
and (unique) maximal dissection are 9 and 10 respectively.
Proof. The polytopes constructed are quite similar to P 4 constructed earlier
except that Q 4 is non-regular (in part 2) and the segments u 1 u 2 and v 1 v 2 are longer
and are not orthogonal, thus ending with dierent polytopes. The polytopes are
shown in Figure 2.6. Figure 2.7 describes a maximal dissection of each of them, in
ve parallel slices. Observe that both polytopes have four vertices in the plane
and another four in the plane y = 1. Hence, the rst and last slices in parts (a) and
(b) of

Figure

2.7 completely describe the polytope.
e
s
e
s
Fig. 2.6. The two polytopes in Proposition 2.3.
(1) The vertices in the planes quadrangles whose
only integer points are the four vertices. This proves that the eight points are in
convex position and that the polytope P contains no integer point other than its
vertices. Let us now prove the assertions on maximal dissections and triangulations
of
(a) Consider the paths of length three are
monotone respectively in the directions orthogonal to v 1 v 2 and u 1 u 2 . Using them,
u2
s
e
(a)
(b)
y y y y y
Fig. 2.7. Five 2-dimensional slices of the maximal dissections of the polytopes in Proposition
2.3. The rst and last slices are two facets of the polytopes containing all the vertices.
we can construct two triangulations of size ve of the polytopes conv(nsewv 1
they do not ll P completely. There is space
left for the tetrahedra swv 1 u 1 and env 2 u 2 . This gives a dissection of P with twelve
tetrahedra. All the tetrahedra are unimodular, so no bigger dissection is possible.
(b) A triangulation of size 11 can be obtained using the same idea as above, but
with paths v and u of lengths three and two respectively, which can be taken from
the same triangulation of the square nswe.
To prove that no triangulation has bigger size, it su-ces to show that P does not
have any unimodular triangulation. This means all tetrahedra have volume 1=6. We
start by recalling a well-known fact (see Corollary 4.5 in [25]). A lattice tetrahedron
has volume 1=6 if and only if each of its vertices v lies in a consecutive lattice plane
parallel to the supporting plane of the opposite facet to v. Two parallel planes are
said to be consecutive if their equations are ax+ by
Suppose that T is a unimodular triangulation of P . We will rst prove that
the triangle u 1 u 2 e is in T . The triangular facet u 1 lying in the hyperplane
has to be joined to a vertex in the plane x 1. The two
possibilities are e and v 1 . With the same argument, if the tetrahedron u 1 u 2 sv 1 is in
which lies in the hyperplane 2x will be joined to a
vertex in 2x 2, and the only one is e. This nishes the proof that u 1
is a triangle in T . Now, u 1 u 2 e is in the plane x must be joined to a
vertex in i.e. to w. Hence u 1 u 2 ew is in T and, in particular, T uses the
edge ew. P is symmetric under the rotation of order two on the axis
g.
Applying this symmetry to the previous arguments we conclude that T uses the edge
ns too. But this is impossible since the edges ns and ew cross each other.
(2) This polytope almost ts the description of P 4 , except for the fact that the
edges intersect the boundary and not the interior of the planar quadrangle
nsew. With the general techniques we have described, it is easy to construct halving
dissections of this polytope with sizes from 6 to 10. Combinatorially, the polytope
is a 4-antiprism. Hence, Proposition 4.3 shows that its minimal triangulation has 7
tetrahedra. The rest of the assertions in the statement were proved using the integer
programming approach proposed in [8], which we describe in Remark 4.5. We have
also veried them by enumerating all triangulations [19, 29]. It is interesting to
observe that if we perturb the coordinates a little so that the planar quadrilateral
becomes a tetrahedron with the right orientation and without changing the
face lattice of the polytope, then the following becomes a triangulation with ten
3. Bounds for the size of a dissection. Let D be a dissection of a d-polytope
. Say two (d 1)-simplices S 1 and S 2 of D intersect improperly in a (d 1)-
hyperplane H if both lie in H , are not identical, and they intersect with non-empty
relative interior. Consider the following auxiliary take as nodes the (d 1)-
simplices of a dissection, and say that two (d 1)-simplices are adjacent if they
intersect improperly in certain hyperplane. A mismatched region is the subset of R d
that is the union of (d 1)-simplices over a connected component of size larger than
one in such a graph. Later, in Proposition 3.4 we will show some of the complications
that can occur in higher dimensions.
Dene the simplicial complex of a dissection as all the simplices of the dissection
together with their faces, where only faces that are identical (in R d ) are identied.
This construction corresponds intuitively to an in
ation of the dissection where for
each mismatched region we move the two groups of (d 1)-simplices slightly apart
leaving the relative boundary of the mismatched region joined. Clearly, the simplicial
complex of a dissection may be not homeomorphic to a ball.
The deformed d-simplices intersect properly, and the mismatched regions become
holes. The numbers of vertices and d-simplices do not change.
Lemma 3.1. All mismatched regions for a dissection of a convex 3-polytope P
are convex polygons with all vertices among the vertices of P . Distinct mismatched
regions have disjoint relative interiors.
Proof. Let Q be a mismatched region and H the plane containing it. Since a
mismatched region is a union of overlapping triangles, it is a polygon in H with a
connected interior. If two triangles forming the mismatched region have interior points
in common, they should be facets of tetrahedra in dierent sides of H . Otherwise, the
two tetrahedra would have interior points in common, contradicting the denition of
dissection. Triangles which are facets of tetrahedra in one side of H cover Q. Triangles
coming from the other side of H also cover Q.
take triangles coming from one side. As mentioned above, they have no
interior points in common. Their vertices are among the vertices of the tetrahedra
in the dissection, thus among the vertices of the polytope P . Hence, the vertices of
the triangles are in convex position, thus the triangles are forming a triangulation of
a convex polygon in H whose vertices are among the vertices of P .
For the second claim, suppose there were distinct mismatched regions having an
interior point in common. Then their intersection should be an interior segment for
Let Q be one of the mismatched regions. It is triangulated in two dierent
ways each coming from the tetrahedra in one side of the hyperplane. The triangles
in either triangulation cannot intersect improperly with the interior segment. Thus
the two triangulations of Q have an interior diagonal edge in common. This means
the triangles in Q consists of more than one connected components of the auxiliary
graph, contradicting the denition of mismatched region.
Proposition 3.2.
1. The size of a mismatching dissection D of a convex 3-polytope with n vertices
is at least n 2.
2. The size of a dissection of a 3-polytope with n vertices is bounded from above
by n 2 .
Proof. (1) Do an in
ation of each mismatched region. This produces as many holes
as mismatched regions, say m of them. Each hole is bounded by two triangulations
of a polygon. This is guaranteed by the previous lemma. Denote by k i the number of
vertices of the polygon associated to the i-th mismatched region. In each of the holes
introduce an auxiliary interior point. The point can be used to triangulate the interior
of the holes by lling in the holes with the coning of the vertex with the triangles it
sees. We now have a triangulated ball.
Denote by jDj the size of the original dissection. The triangulated ball has then
total. The number of interior edges of this triangulation
is the number of interior edges in the dissection, denoted by e i (D), plus the new
additions, for each hole of length k i we added k i interior edges. In a triangulation T of
a 3-ball with n boundary vertices and n 0 interior vertices, the number of tetrahedra jT j
is related to the number of interior edges e i of T by the formula: jT
The proof is a simple application of Euler's formula for triangulated 2-spheres and
3-balls and we omit the easy details.
Thus, we have the following equation:
3:
This can be rewritten as
Taking into account
that e i (D)
(because diagonals in a polygon are interior edges of the
dissection), we get an inequality
3:
Finally note that in a mismatching dissection we have m  1 and k i  4. This
gives the desired lower bound.
(2) Now we look at the proof of the upper bound on dissections. Given a 3-
dissection, we add tetrahedra of volume zero to complete to a triangulation with
at
simplices that has the same number of vertices. One can also think we are lling in
the holes created by an in
ation with (deformed) tetrahedra.
The lemma states that mismatched regions were of the shape of convex polygons.
The 2-simplices forming a mismatched region were divided into two groups (those
becoming apart by an in
ation). The two groups formed dierent triangulations of a
convex polygon, and they had no interior edges in common. In this situation, we can
make a sequence of
ips (see [17]) between the two triangulations with the property
that any edge once disappeared does not appear again (see Figure 3.1). We add one
abstract, volume zero tetrahedron for each
ip, and obtain an abstract triangulation
of a 3-ball.
The triangulation with
at simplices we created is a triangulated 3-ball with n
vertices. By adding a new point in a fourth dimension, and coning from the boundary
2-simplices to the point, we obtain a triangulated 3-sphere containing the original 3-
ball in its boundary. From the upper bound theorem for spheres (for an introduction
Fig. 3.1. Filling in holes with tetrahedra according to
ips.
to this topic see [30]) its size is bounded from above by the number of facets of a
cyclic 4-polytope minus 2n 4, the number of 2-simplices in the boundary of D. The
4-dimensional cyclic polytope with vertices is well-known to have (n
2)=2 facets (see [11, page 63]), which completes the proof after a trivial algebraic
calculation.
Open Problem 3.3. What is the correct upper bound theorem for dissections of
d-dimensional polytopes with d  4?
In our proof of Proposition 3.2 we built a triangulated PL-ball from a three-dimensional
dissection, using the
ip connectivity of triangulations of a convex n-gon.
Unfortunately the same cannot be applied in higher dimensions as the
ip connectivity
of triangulations of d-polytopes is known to be false for convex polytopes in general
[22]. But even worse, the easy property we used from Lemma 3.1 that mismatched
regions are convex polyhedra fails in dimension d  4.
Proposition 3.4. The mismatched regions of a dissection of a convex 4-polytope
can be non-convex polyhedra.
Proof. The key idea is as follows: suppose we have a 3-dimensional convex polytope
P and two triangulations T 1 and T 2 of it with the following properties: removing
from P the tetrahedra that T 1 and T 2 have in common, the rest is a non-convex
polyhedron P 0 such that the triangulations T 0
2 of it obtained from T 1 and
do not have any interior 2-simplex in common (actually, something weaker would
su-ce: that their common interior triangles, if any, do not divide the interior of the
polytope).
In these conditions, we can construct the dissection we want as a bipyramid over
to one of the apices and T 2 to the other one. The bipyramid over the
non-convex polyhedron P 0 will be a mismatched region of the dissection.
For a concrete example, start with Schonhardt's polyhedron whose vertices are
labeled in the lower face and 4; 5; 6 in the top face. This is a non-convex
polyhedron made, for example, by twisting the three vertices on the top of a triangular
prism. Add two antipodal points 7 and 8 close to the \top" triangular facets (those
not breaking the quadrilaterals see Figure 3.2). For example, take as coordinates
for the points
Let P 0 be this non-convex polyhedron and let T 0
1468g.
1 cones vertex 7 to the rest of the boundary of P 0 , and T 0
vertex 8. Any
common interior triangle of T 0
would use the edge 78. But the link of 78 in
contains only the points 1, 2 and 3, and the link in T 0
contains only 4, 5 and 6.
Let P be the convex hull of the eight points, and let T 1 and T 2 be obtained from
2 by adding the three tetrahedra 1245, 2356 and 1346.
Fig. 3.2. The mismatched region of a four-dimensional dissection.
4. Optimal dissections for specic polytopes. The regular cube has been
widely studied for its smallest dissections [12, 14]. This receives the name of simplexity
of the cube. In contrast, because of the type of simplices inside a regular d-cube, a
simple volume argument shows that the maximal size of a dissection is d!, the same
as for triangulations. On the other hand, we know that the size of the maximal
triangulation of a combinatorial cube can be larger than that: For example, the
combinatorial 3-cube obtained as the prism over a trapezoid (vertices on a parabola
for instance) has triangulations of size 7. Figure 4.1 shows a triangulation with 7
simplices for those coordinatizations where the edges AB and GH are not coplanar.
The tetrahedron ABGH splits the polytope into two non-convex parts, each of which
can be triangulated with three simplices. To see this, suppose that our polytope is
a very small perturbation of a regular 3-cube. In the regular cube, ABGH becomes
a diagonal plane which divides the cube into two triangular prisms ABCDGH and
ABEFGH . In the non-regular cube, the diagonals AH and BG, respectively, become
non-convex. Any pair of triangulations of the two prisms, each using the corresponding
diagonal, together with tetrahedron ABGH give a triangulation of the perturbed cube
with 7 tetrahedra. The boundary triangulation is shown in the
at diagram. It is
worth noticing that for the regular cube the boundary triangulation we showed does
not extend to a triangulation of the interior.
A
F
G
A
F
G
Fig. 4.1. A triangulation of a combinatorial 3-cube into seven tetrahedra.
One can then ask, what is the general growth for the size of a maximal dissection
of a combinatorial cube? To answer this question, at least partially, we use the above
construction and we adapt an idea of M. Haiman, originally devised to produce small
triangulations of regular cubes [12]. The idea is that from triangulations of a d 1 -
cube and a d 2 -cube of sizes s 1 and s 2 respectively we can get triangulations of the
rst subdividing it into s 1 s 2 copies of the product of two simplices
of dimensions d 1 and d 2 and then triangulating each such piece. We recall that any
triangulation of the Cartesian product of a d 1 -simplex and a d 2 -simplex has d1+d2
maximal simplices. Hence, in total we have a triangulation of the (d 1
maximal simplices. Recursively, if one starts with a triangulation of
size s of the d-cube, one obtains triangulations for the rd-cube of size (rd)!( s
In
Haiman's context one wants s to be small, but here we want it to be big.
More precisely, denote by f(d) the function max C: d-cube (max T of C jT j) and call
Haiman's argument shows that if f(d 1
dierently, that g(d 1
. The value on the right hand
side is the weighted geometric mean of g(d 1 ) and g(d 2 ). In particular, if both g(d 1 )
and g(d 2 ) are  1 and one of them is > 1 then g(d 1
We have constructed above a triangulation of size 7 for the Klee-Minty 3-cube,
which proves g(3)  3
Haiman's idea we can now construct
\large" triangulations of certain 4-cubes and 5-cubes, which prove respectively that
equal to one and
two respectively). Finally, since any d > 5 can be expressed as a sum of 3's and 4's,
we have g(d)  minfg(3); g(4)g  1:039 for any d > 5. Hence:
Proposition 4.1. For the family of combinatorial d-cubes with d > 2 the function
admits the lower bound f(d)  c d d! where
c  1:031.
Exactly as in Haiman's paper, the constant c can be improved (asymptotically)
if one starts with larger triangulations for the smaller dimensional cubes. Using
computer calculations (see Remark 4.5), we obtained a maximal triangulation for the
Klee-Minty 4-cube with 38 maximal simplices, which shows that g(d)  4
1:122 for every d divisible by 4 (see [1] for a complete study of this family of cubes).
We omit listing the triangulation here but it is available from the authors by request.
Open Problem 4.2. Is the sequence g(d) bounded? In other words, is there an
upper bound of type c d d! for the function f(d)? Observe that the same question for
minimal triangulations of the regular d-cube (whether there is a lower bound of type
c d d! for some c > 0) is open as well. See [26] for the best lower bound known.
We continue our discussion with the study of optimal triangulations for three-dimensional
prisms and antiprisms. We will call an m-prism any 3-polytope with
the combinatorial type of the product of a convex m-gon with a line segment. An m-
antiprism will be any 3-polytope whose faces are two convex m-gons and 2m triangles,
each m-gon being adjacent to half of the triangles. Vertices of the two m-gons are
connected with a band of alternately up and down pointing triangles.
Each such polyhedron has a regular coordinatization in which all the faces are
regular polygons, and a realization space which is the set of all possible coordinatiza-
tions that yield the same combinatorial information [20]. Our rst result is valid in
the whole realization space.
Proposition 4.3. For any three-dimensional m-prism, in any of its possible
coordinatizations, the number of tetrahedra in a minimal triangulation is 2m 5+d m
e.
For any three-dimensional m-antiprism, in any of its possible coordinatizations,
the number of tetrahedra in a minimal triangulation is 3m 5.
Proof. In what follows we use the word cap to refer to the m-gon facets appearing
in a prism or antiprism. We begin our discussion proving that any triangulation of
the prism or antiprism has at least the size we state, and then we will construct
triangulations with exactly that size.
We rst prove that every triangulation of the m-prism requires at least 2m 5
We call a tetrahedron of the m-prism mixed if it has two vertices on
the top cap and two vertices on the bottom cap of the prism, otherwise we say that
the tetrahedron is top-supported when it has three vertices on the top (respectively
bottom-supported). For example, Figure 4.2 shows a triangulation of the regular 12-
prism, in three slices. Parts (a) and (c) represent, respectively, the bottom and top
caps. Part (b) is the intersection of the prism with the parallel plane at equal distance
to both caps. In this intermediate slice, bottom or top supported tetrahedra appear
as triangles, while mixed tetrahedra appear as quadrilaterals.
(b)
(a) (c)
Fig. 4.2. A minimal triangulation of the regular 12-prism.
Because all triangulations of an m-gon have m 2 triangles there are always
exactly 2m 4 tetrahedra that are bottom or top supported. In the rest, we show
there are at least d m
mixed tetrahedra. Each mixed tetrahedra marks an edge
of the top, namely the edge it uses from the top cap. Of course, several mixed
tetrahedra could mark the same top edge. Group together top-supported tetrahedra
that have the same bottom vertex. This grouping breaks the triangulated top m-gon
into polygonal regions. Note that every edge between two of these regions must be
marked. For example, in part (c) of Figure 4.2 the top cap is divided into 6 regions
by 5 marked edges (the thick edges in the Figure). Let r equal the number of regions
under the equivalence relation we set. There are r 1 interior edges separating the
r regions, and all of them are marked. Some boundary edges of the top cap may be
marked too (none of them is marked in the example of Figure 4.2).
We can estimate the marked edges in another way: There are m edges on the
boundary of the top, which appear partitioned among some of the regions (it could
be the case some region does not contain any boundary edge of the m-gon). We claim
that no more than two boundary edges per region will be unmarked (). This follows
because a boundary edge is not marked only when the top supported tetrahedron that
contains it has the point in the bottom cap that is directly under one of the vertices
of the edge. In a region, at most two boundary edges can satisfy this. Hence we get
at least m 2r marked edges on the boundary of the top and at least (r
marked edges in total. Thus the number of mixed tetrahedra is at
least the maximum of r 1 and m r 1. In conclusion, we get that, indeed, the
number of mixed tetrahedra is bounded below by d m
e 1. Note that we only use
the combinatorics and convexity of the prism in our arguments. We will show that
minimal triangulations achieve this lower bound, but then, observe that if m is even, in
a minimal triangulation we must have no boundary edge can be marked,
as is the case in Figure 4.2. If m is odd, then we must have r 2 f(m 1)=2; (m+1)=2g
and at most one boundary edge can be marked.
The proof that any triangulation of an m-antiprism includes at least 3m 5 tetrahedra
is similar. There are 2m 4 top-supported and bottom-supported tetrahedra
in any triangulation and there are r 1 marked edges between the regions in the
top. The only dierence is that, instead of claim (), one has at most one unmarked
boundary edge per region. Thus there are at least m r marked edges in the boundary
of the top, and in total at least (r marked edges in the top.
Hence there exist at least (2m 4)+(m in any triangulation.
For an m-antiprism we can easily create a triangulation of size 3m 5 by choosing
any triangulation of the bottom m-gon and then coning a chosen vertex v of the top
m-gon to the m 2 triangles in that triangulation and to the 2m 3 triangular facets of
the m-antiprism which do not contain v. This construction is exhibited in Figure 4.3.
Parts (a) and (c) show the bottom and top caps triangulated (each with its 5 marked
edges) and part (b) an intermediate slice with the 5 mixed tetrahedra appearing as
quadrilaterals.
(c)
(b)
(a)
Fig. 4.3. A minimal triangulation of the regular 6-antiprism.
For an m-prism, let u i and v i , denote the top and bottom vertices
respectively, so that the vertices of each cap are labeled consecutively and u
always an edge of the prism.
If m is even we can chop o the vertices u i for odd i and v j for even j, so that
the prism is decomposed into m tetrahedra and an ( m)-antiprism. The antiprism can
be triangulated into 3m5 tetrahedra, which gives a triangulation of the prism into
5m5 tetrahedra, as desired. Actually, this is how the triangulation of Figure 4.2
can be obtained from that of Figure 4.3.
If m is odd we do the same, except that we chop o only the vertices
and vertex is chopped in the edge um v m ). This produces m 1
tetrahedra and an ( m+1
)-antiprism. We triangulate the antiprism into 3m+3
tetrahedra and this gives a triangulation of the m-prism into 5m+15 tetrahedra.
We have seen that the coordinates are not important when calculating minimal
triangulations of the three-dimensional prisms and antiprisms. On the other hand,
the dierence in size of the maximal triangulation can be quite dramatic. Below we
prove that in certain coordinatizations it is roughly m 2and show experimental data
indicating that for the regular prism it is close to m 2Proposition 4.4. Let Am be a prism of order m, with all its side edges parallel.
1. The size of a maximal triangulation of Am is bounded as
2. The upper bound is achieved if the two caps (m-gon facets) are parallel and
there is a direction in which the whole prism projects onto one of its side
quadrangular facets. (For a concrete example, let one of the m-gon facets
have vertices on a parabola and let Am be the product of it with a segment).
Proof. Let the vertices of the prism be labeled um and v so that
the u i 's and the v j 's form the two caps, vertices in each cap are labeled consecutively
and u i v i is always a side edge.
For the upper bound in part (1), we have to prove that a triangulation of Am has
at most m 2 +m 62m diagonals. The possible diagonals are
the edges is not in f1; 0; 1g modulo m. This gives exactly twice the
number we want. But for any i and j the diagonals u
one of them can appear in each triangulation.
We now prove that the upper bound is achieved if Am is in the conditions of part
(2). In fact, the condition on Am that we will need is that for any 1  i < j  k <
l  m, the point v j sees the triangle v i u k u l from the same side as v k and v l (i.e. \from
above" if we call top cap the one containing the v i 's). With this we can construct a
triangulation with
First cone the vertex v 1 to any triangulation of the bottom cap (this gives m 2
tetrahedra). The m 2 upper boundary facets of this cone are visible from v 2 , and
we cone them to it (again m 2 tetrahedra). The new m 2 upper facets are visible
from v 3 and we cone them to it (m 2 tetrahedra more). Now, one of the upper
facets of the triangulation is of the upper cap, but the other m 3 are
visible from v 4 , so we cone them and introduce m 4 tetrahedra. Continuing the
process, we will introduce coning the vertices
which gives a total of
The triangulation we have constructed is the placing triangulation [17] associated
to any ordering of the vertices nishing with dierent description of the
same triangulation is that it cones the bottom cap to v 1 , the top cap to um , and its
mixed tetrahedra are all the possible 1. This gives
We nally prove the lower bound stated in part (1). Without loss of general-
ity, we can assume that our prism has its two caps parallel (if not, do a projective
transformation keeping the side edges parallel). Then, Am can be divided into two
prisms in the conditions of part (2) of sizes k and l with 2: take any
two side edges of Am which posses parallel supporting planes and cut Am along the
plane containing both edges. By part (2), we can triangulate the two subprisms with
respectively, taking care that the two triangulations
use the same diagonal in the dividing plane. This gives a triangulation of Am with
This expression achieves its minimum
when k and l are as similar as possible, i.e.
Plugging
these values in the expression gives a triangulation of size
l
Based on an integer programming approach we can compute maximal triangulations
of specic polytopes (see remark at the end of the article). Our computations
with regular prisms up to show that the size of their maximal triangulations
achieve the lower bound stated in part (1) of Proposition 4.4 (see Table 4.1). In
other words, that the procedure of dividing them into two prisms of sizes b m
and d m
in the conditions of part (2) of Proposition 4.4 and triangulating the
subprisms independently yields maximal triangulations.
We have also computed maximal sizes of triangulations for the regular m-antiprisms
up to which turn out to follow the formula
. A construction
of a triangulation of this size for every m can be made as follows: Let the vertices
of the regular m-antiprism be labeled um and v so they are forming
the vertices of the two caps consecutively in this order and v i u i and u i v i+1 are side
edges. We let v . The triangulation is made by placing the vertices in any
ordering nishing with . The tetrahedra used are the
bottom-supported tetrahedra with apex v 1 , top-supported tetrahedra with apex u d me
and the mixed tetrahedra
We conjecture that these formulas for regular base prisms and antiprisms actually
give the sizes of their maximal triangulations for every m, but we do not have a proof.
Prism (regular base) 43 50
Antiprism (regular base) 4 8 12 17 22 28 34 41 48 56

Table
Sizes of maximal triangulations of prisms and antiprisms.
Remark 4.5. How can one nd minimal and maximal triangulations in specic
instances? The approach we followed for computing Tables 1.1 and 4.1 and some
of the results in Proposition 2.3 is the one proposed in [8], based on the solution of
an integer programming problem. We think of the triangulations of a polytope as
the vertices of the following high-dimensional polytope: Let A be a d-dimensional
polytope with n vertices. Let N be the number of d-simplices in A. We dene PA
as the convex hull in R N of the set of incidence vectors of all triangulations of A.
For a triangulation T the incidence vector v T has coordinates (v T
and (v T . The polytope PA is the universal polytope dened in
general by Billera, Filliman and Sturmfels [3] although it appeared in the case of
polygons in [7]. In [8], it was shown that the vertices of PA are precisely the integral
points inside a polyhedron that has a simple description in terms of the oriented
matroid of A (see [8] for information on oriented matroids). The concrete integer
programming problems were solved using C-plex Linear Solver TM . The program to
generate the linear constraints is a small C ++ program written by Samuel Peterson
and the rst author. Source code, brief instructions, and data les are available via
ftp at http://www.math.ucdavis.edu/~deloera. An alternative implementation
by A. Tajima is also available [27, 28]. He used his program to corroborate some of
these results.
It should be mentioned that a simple variation of the ideas in [8] provides enough
equations for an integer program whose feasible vertices are precisely the 0=1-vectors
of dissections. The incidence vectors of dissections of conv(A), for a point set A,
are just the 0=1 solutions to the system of equations hx; v T are the
incidence vectors for every regular triangulation T of the Gale transform A  (regular
triangulations in the Gale transform are the same as chambers in A). Generating all
these equations is as hard as enumerating all the chambers of A. Nevertheless, it is
enough to use those equations coming from placing triangulations (see [23, Section
3.2]), which gives a total of about n d+1 equations if A has n points and dimension d.

Acknowledgments

. We are grateful to Alexander Below and Jurgen Richter-
Gebert for their help and ideas in the proofs of Proposition 3.2 and 3.4. Alexander
Below made Figure 3.2 using the package Cinderella. The authors thank Akira Tajima
and Jorg Rambau for corroborating many of the computational results. We thank
Samuel Peterson for his help with our calculations. Finally, we thank Hiroshi Imai,
Bernd Sturmfels, and Akira Tajima for their support of this project.



--R

Deformed products and maximal shadows of polytopes
An algorithmic theory of lattice points in polyhedra
Constructions and complexity of secondary poly- topes
Minimal simplicial dissections and triangulations of convex 3-polytopes

New York
Triangulations (tilings) and certain block triangular matrices

Tetrahedrizing point sets in three di- mensions
binary covers of rational polyhedral cones

A simple and relatively e-cient triangulation of the n-cube
The Cayley trick
Simplexity of the cube
Triangulations of integral polytopes and Ehrhart polynomials

Subdivisions and triangulations of polytopes
Triangulations for the cube
TOPCOM: a program for computing all triangulations of a point set

On triangulations of the convex hull of n points
A point con
Triangulations of oriented matroids



Optimality and integer programming formulations of triangulations in general di- mension
Optimizing geometric triangulations by using integer programming
Enumerating triangulations for products of two simplices and for arbitrary con

--TR

--CTR
Mike Develin, Note: maximal triangulations of a regular prism, Journal of Combinatorial Theory Series A, v.106 n.1, p.159-164, April 2004
Jesus A. De Loera , Elisha Peterson , Francis Edward Su, A polytopal generalization of Sperner's lemma, Journal of Combinatorial Theory Series A, v.100 n.1, p.1-26, October 2002
archimedean solid;antiprism;lattice polytope;mismatched region;combinatorial d-cube;prism;dissection;triangulation