The Polytope of All Triangulations

of a Point Configuration

Jesús A. de Loera^{1}, Serkan Hoşten^{1}, Francisco Santos^{2}, Bernd Sturmfels^{3}

Received: December 9, 1995 Revised: March 4, 1996

Communicated by Günter M. Ziegler

Abstract. We study the convex hull P_{A} of the 0-1 incidence vectors of all triangulations of a point configuration A. This was called the universal polytope in [4]. The affine span of P_{A} is described in terms of the cocircuits of the oriented matroid of A. Its intersection with the positive orthant is a quasi-integral polytope Q_{A} whose integral hull equals P_{A}. We present the smallest example where Q_{A} and P_{A} differ. The duality theory for regular triangulations in [5] is extended to cover all triangulations. We discuss potential applications to enumeration and optimization problems regarding all triangulations.

1991 Mathematics Subject Classification: Primary 52B55; Secondary 90C27.

1 Introduction

We are interested in the set of all triangulations of a configuration A = {a_{1}, …, a_{n}} ⊂ R^{d}. The subset of regular triangulations is well-understood thanks to its bijection with the vertices of the secondary polytope (see [7, Chapter 7] and [16, Lecture 9]). But non-regular triangulations remain a mystery: for instance, it is still unknown whether any two triangulations of A can be connected by a sequence of bistellar flips [12]. Non-regular triangulations are abundant: if A is the vertex set of the cyclic polytope C_{4n−4}(4n), there are at least 2^{n} triangulations (Proposition 5.10 in this article), while the number of regular triangulations is O(n^{4}).

1Supported in part by the National Science Foundation 2Supported in part by the Spanish Dirección General de Investigacion Científica y Técnica 3Supported in part by the David and Lucille Packard Foundation and the National Science Foundation

Documenta Mathematica 1 (1996) 103–119

One approach in understanding non-regular triangulations is to replace the secondary polytope by a larger polytope P_{A} whose vertices are in bijection with all triangulations of A. The polytope P_{A} is isomorphic to the universal polytope introduced by Billera, Filliman and Sturmfels [4]. They expressed the secondary polytope as a projection of P_{A} and they showed dim(P_{A}) = \binom{n−1}{d+1} when A is in general position. We shall now fix some notation, and define the polytope P_{A}.

Throughout this paper A ⊂ R^{d} will denote a d-dimensional configuration of n possibly repeated points. By a k-simplex we mean a sub-configuration of A consisting of k + 1 affinely independent points. A triangulation of A is a collection T of dsimplices whose convex hulls cover conv(A) and intersect properly: for any σ and τ in T we have conv(σ ∩ τ) = conv(σ) ∩ conv(τ). Let Δ(A) denote the collection of d-simplices in A. We define P_{A} as the convex hull in R^{Δ(A)} of the set of incidence vectors of all triangulations of A. For a triangulation T the incidence vector v_{T} has coordinates (v_{T})_{σ} = 1 if σ ∈ T and (v_{T})_{σ} = 0 if σ ∉ T. We also consider the polytope Q_{A} = aff(P_{A}) ∩ R_{+}^{Δ(A)}, which is the linear programming relaxation of P_{A}. We denote by M(A) the oriented matroid of affine dependencies of the point configuration A.

We first present linear equations defining the affine hull aff(P_{A}) of P_{A}. These equations involve the cocircuits (see [6, Chapter 1] or [16, Lecture 6]) of M(A): for any τ which is a (d−1)-simplex of A, let H_{τ} be the hyperplane that contains τ and let H_{τ}^{+} and H_{τ}^{−} denote the two open half-spaces defined by H_{τ}. We recall that the cocircuits of the oriented matroid M(A) are the resulting partitions (A ∩ H_{τ}^{+}, A ∩ H_{τ} , A ∩ H_{τ}^{−}) of A. Consider the following linear form:

Co_{τ} := ∑_{σ=τ∪{a}, a∈A∩H_{τ}^{+}} x_{σ} − ∑_{σ=τ∪{a}, a∈A∩H_{τ}^{−}} x_{σ}  (1)

We call Co_{τ} the cocircuit form associated with the (d−1)-simplex τ. If conv(τ) ∩ int(conv(A)) ≠ ∅, we say that τ is an interior (d − 1)-simplex. In this case neither of the two sums in (1) is void. Moreover, every triangulation T of A contains either no d-simplex containing τ or exactly two, one in the first sum and one in the second. Thus Co_{τ} vanishes at the incidence vector v_{T} of every triangulation of A, and hence, on aff(P_{A}). We call the equations Co_{τ} = 0, for interior (d−1)-simplices τ, the interior cocircuit equations. We summarize our main results:

Theorem 1.1 Let A be a point configuration with the above conventions.

(i) The affine span of P_{A} in R^{Δ(A)} is defined by the linear equations Co_{τ} = 0 for every interior (d − 1)-simplex τ, together with one non-homogeneous linear equation valid on P_{A}.

(ii) P_{A} coincides with the integral hull of Q_{A}; i.e., the lattice points in Q_{A} are precisely the incidence vectors of triangulations of A.

(iii) Two triangulations T_{1} and T_{2} of A are neighbors in the edge graph of P_{A} if and only if they are neighbors in the edge graph of Q_{A}.

(iv) For the case of the n-gon and configurations with at most d + 3 points, we have Q_{A} = P_{A}. This is not true in general for n ≥ d + 4 ≥ 6.

The following three types of non-homogeneous equations may be used to complete the description of aff(P_{A}) in part (i) of Theorem 1.1: If τ is a non-interior (d − 1)- simplex and conv(τ) is a facet of conv(A), then the cocircuit form Co_{τ} has constant value equal to ±1 on P_{A}. This produces new valid equations for aff(P_{A}) which we call boundary cocircuit equations. They can be expressed in the form

∑_{σ=τ∪{a}, a∈A\τ} x_{σ} = 1.  (2)

Another set of valid equations for aff(P_{A}) can be obtained as follows: let p ∈ conv(A) be a point not lying in the convex hull of any (d − 1)-simplex of A. Every triangulation of A satisfies the equation:

∑_{σ∈Δ(A), p∈conv(σ)} x_{σ} = 1.  (3)

Recall that the chamber complex of A is the common refinement of all triangulations of A (see [1],[5]). We call the equations of type (3) chamber equations, because the simplices in the sum only depend on the chamber in which p lies. Note that the boundary cocircuit equations (2) are a particular case of chamber equations.

Finally, if we denote by vol(·) the standard volume form on R^{d}, the following volume equation is satisfied by every triangulation of A:

∑_{σ∈Δ(A)} vol(conv(σ)) x_{σ} = vol(conv(A)).  (4)

Remark 1.2 The (interior and boundary) cocircuit equations depend only on the oriented matroid M(A) of affine dependencies of A. This holds neither for the volume equation nor for chamber equations: for example, all configurations consisting on the six vertices of a convex planar hexagon have the same oriented matroid, while the number of chambers can be 24 or 25, depending on the coordinates of the vertices.

Clearly, if A has no simplicial facets, then there are no boundary cocircuit equations. However, every configuration A has some chamber equations which can be obtained from the oriented matroid M(A). (Such chambers arise from lexicographic extensions; see [6, Figure 7.2.2, page 296].) Any of them, together with the interior cocircuit equations, will provide a description of aff(P_{A}) in terms of M(A). Part (ii) of Theorem 1.1 implies that this yields a description of P_{A} itself in terms of M(A).

In Section 2 we examine the affine span of P_{A} and we prove part (i) of Theorem 1.1. A surprising consequence (Corollary 2.3) is that aff(P_{A}) is spanned by the regular triangulations only. This implies the formula dim(P_{A}) = \binom{n−1}{d+1} when A is in general position. Section 3 contains the proof of parts (ii) and (iii) in Theorem 1.1. As a consequence of part (iii) we obtain a combinatorial characterization of the edges of P_{A} (Theorem 3.3). Section 4 contains the proof of part (iv). We also discuss computational issues regarding the enumeration of triangulations and the optimization of linear cost functions over P_{A}. In Section 5 we present a duality theory relating (non-regular) triangulations of A with (virtual) chambers in the Gale transform of A.

2 Equations defining the affine span of P_{A}

We introduce now some basic definitions and properties concerning regular triangulations. For a more detailed description and the relevant background the reader may consult [4],[5],[7, Chapter 7],[9] and [16].

A regular triangulation of A is a triangulation which is obtained by projecting the lower envelope of a (d+1)-dimensional simplicial polytope onto conv(A). In other words, a triangulation is regular if it supports a piecewise convex linear functional.

In [7, Chapter 7] the collection of regular triangulations of a point configuration is identified with the vertex set of a polytope Σ(A) of dimension n − d − 1 embedded in R^{n}. This polytope, called the secondary polytope, is a projection of P_{A} [4]. The projection map π : R^{Δ(A)} → R^{A} is given by π(e_{σ}) = vol(σ) ∑_{a∈σ} e_{a}, where e_{σ} and e_{a} denote the standard basis vectors.

A characterization of the edges of Σ(A) is given in [7, Chapter 7]. This uses the notions of circuits and bistellar flips. We only define bistellar flips in the general position case: a circuit of the point configuration A is a minimal affinely dependent set. If A is in general position circuits are subsets of cardinality d + 2. The unique (up to scaling factor) affine dependency equation satisfied by a circuit Z splits it into two subsets Z^{+} and Z^{−} consisting of the points which have positive and negative coefficients respectively. Any circuit Z has exactly two triangulations t(Z)^{+} = {Z \ {a}, a ∈ Z^{+}} and t(Z)^{−} = {Z \ {a}, a ∈ Z^{−}}. If a triangulation T of A contains one of the two triangulations of a circuit Z (say t(Z)^{+}), then T′ = T \ t(Z)^{+} ∪ t(Z)^{−} is again a triangulation of A. The operation that passes from T to T′ (or vice versa) is called a bistellar flip. Two regular triangulations are neighbors in the 1-skeleton of the secondary polytope Σ(A) if and only if they differ by a bistellar flip. This implies that any two regular triangulations can be transformed to one another by a finite sequence of bistellar flips. It is unknown whether this property is true for non-regular triangulations.

Our next goal is to prove part (i) of Theorem 1.1. We first state a lemma about the behavior of triangulations under the matroidal operations of deletion A ↦ A\a_{i} and contraction A ↦ A/a_{i}, where a_{i} is a vertex of A. We regard A/a_{i} as a configuration of typically n−1 points (maybe less, if a_{i} was a repeated point) in affine (d − 1)-space. The convex hull of A/a_{i} is the vertex figure of conv(A) at a_{i}.

Lemma 2.1 Let a_{1} ∈ A be a vertex of conv(A). Every triangulation of A\a_{1} can be extended to a triangulation of A. Every regular triangulation of A/a_{1} can be extended to a triangulation of A. The latter fails for non-regular triangulations.

Proof: Every (regular or non-regular) triangulation T′ of A\a_{1} can be extended to a triangulation T of A by the placing operation described on page 444 in [9]. In this situation T is regular if and only if T′ is regular.

The extension property of regular triangulations for contractions follows from the identification of the secondary fan of A with the chamber complex of B, where B is a Gale transform of A (see [5], in particular Lemma 3.2 and the paragraph after Lemma 3.4). The reasoning is this: let T′ be a regular triangulation of A/a_{1}. It corresponds to a chamber C_{T′} of B\b_{1}, where b_{1} ∈ B is the point corresponding to a_{1} in the Gale transform. The chamber C_{T′} may split into smaller chambers when passing to the chamber complex of B and any such smaller chamber C_{T} corresponds to a triangulation T of A with T/a_{1} = T′.

To see that regularity is necessary in the previous paragraph, let A ⊂ R^{3} be the configuration a_{1} = (20, 0, 1), a_{2} = (1, 20, 0), a_{3} = (0, 1, 20), a_{4} = (10, 0, 0), a_{5} = (0, 10, 0), a_{6} = (0, 0, 10) and a_{7} = (−10, −10, −10). Let T′ be the triangulation of A/a_{7} given by the triangles {1, 2, 5}, {1, 3, 4}, {1, 4, 5}, {2, 3, 6}, {2, 5, 6}, {3, 4, 6} and {4, 5, 6}. There is no triangulation T of A such that T/a_{7} = T′. The non-convex polyhedron with vertices a_{1}, …, a_{6} and triangular faces determined by the above list, together with the triangle {1, 2, 3}, is the Schönhardt polyhedron [13] which cannot be triangulated without adding a new point.

Part (i) of Theorem 1.1 is a consequence of the following theorem and the existence of non-homogeneous forms vanishing on P_{A}.

Theorem 2.2 Let h = ∑_{σ∈Δ(A)} c_{σ}x_{σ} (c_{σ} ∈ R) be any homogeneous linear form on

R^{Δ(A)}. The following properties are equivalent:

(i) h is a linear combination of the interior cocircuit forms Co_{τ} (1).

(ii) h vanishes on (the incidence vector of) every triangulation of A.

(iii) h vanishes on (the incidence vector of) every regular triangulation of A.

Proof: (i)⇒(ii)⇒(iii) are obvious. We prove (iii)⇒(i).

Let P_{A}^{reg} denote the convex hull of all points v_{T} where T is a regular triangulation of A. Thus P_{A}^{reg} ⊂ P_{A}. Let h = ∑ c_{σ}x_{σ} be any linear form which vanishes on P_{A}^{reg}. We shall prove that h is a linear combination of the interior cocircuit forms using a double induction on n = |A| and d = dim(A). Assume that the statement is true for any configuration of smaller cardinality or smaller dimension.

Let a_{1} be a vertex of conv(A). Let us suppose that A\a_{1} still spans R^{d}. Otherwise P_{A}^{reg} and P_{A\a_{1}}^{reg} are affinely isomorphic and the theorem follows by induction. The interior cocircuit forms Co_{τ} vanish on P_{A}^{reg}. If a_{1} ∉ τ then Co_{τ} involves at most one d-simplex of the form σ = {a_{1}} ∪ τ. Subtracting appropriate multiples of those Co_{τ} from h we get another linear form h_{1} in which the variables x_{σ} corresponding to these simplices do not appear. That is,

h_{1}  = ∑_{{σ:a_{1}∈σ \atop conv(σ\a_{1})⊂ boundary(conv(A))}}c_{σ}x_{σ} + ∑_{σ:a_{1}∉σ} c′_{σ}x_{σ}.

The second sum h_{2} = ∑_{σ:a_{1}∉σ} c′_{σ}x_{σ} is a linear form vanishing on P_{A\a_{1}}^{reg}. Indeed, let T′ be any regular triangulation of A\a_{1}. Pick a regular triangulation T of A that extends T′ as in Lemma 2.1. Since a_{1} is a vertex of conv(A), the triangulation T cannot contain a simplex σ of the form {a_{1}} ∪ τ where conv(τ) is in the boundary of conv(A). This fact together with h_{1}(v_{T}) = 0 implies h_{2}(v_{T}) = 0, and consequently h_{2}(v_{T′}) = 0.

Every cocircuit form Co_{τ} of A\a_{1} is either a cocircuit form of A as well or can be extended to a cocircuit form of A by adding a single variable x_{{a_{1}}∪τ} with the appropriate sign. By induction hypothesis, h_{2} is a linear combination of the cocircuit forms of A\a_{1}. We extend this presentation to a linear combination of cocircuit forms of A, which vanishes on P_{A}^{reg}. We subtract it from h_{1} to get a new form h_{3} which vanishes on P_{A}^{reg} and involves only d-simplices σ of the form a_{1} ∪ τ:

h_{3} = ∑_{σ:a_{1}∈σ} c′′_{σ}x_{σ}.

The assignment τ ↦ {a_{1}}∪τ defines a bijection between the simplices of A/a_{1} and the simplices of A containing a_{1}. Therefore we can interpret h_{3} as a linear form on P_{A/a_{1}}^{reg}. Lemma 2.1 guarantees that h_{3} vanishes on P_{A/a_{1}}^{reg}. By the induction hypothesis, h_{3} is a linear combination of cocircuit forms Co_{τ} of A/a_{1}. We replace each variable x_{τ} in this linear combination by the corresponding variable x_{{a_{1}}∪τ}. This transforms cocircuit forms of A/a_{1} into cocircuit forms Co_{{a_{1}}∪τ} of A. Therefore h_{3} is a linear combination of cocircuit forms of A. This proves Theorem 2.2 and Theorem 1.1 (i).

Corollary 2.3 The linear subspace of R^{Δ(A)} parallel to aff(P_{A}) is spanned by all vectors v_{T} −v_{T′} where T and T′ are regular triangulations of A differing by a bistellar flip.

Proof: It follows from Theorem 2.2 that the linear subspace in question is spanned by all vectors v_{T} − v_{T′} where T and T′ are regular triangulations. Since every pair of regular triangulations is connected by a sequence of bistellar flips, the corollary follows.

Theorem 2.2 implies dim(P_{A}) = |Δ(A)| − R − 1, where R is the rank of the interior cocircuit forms. If the points of A are in general position then |Δ(A)| = \binom{n}{d+1}. In this case the vector v_{T} − v_{T′}, where T and T′ are regular triangulations of A differing by a bistellar flip, equals v_{t(Z)^{+}} − v_{t(Z)^{−}}, where t(Z)^{+} and t(Z)^{−} are the two triangulations of the circuit Z on which the bistellar flip is supported.

Theorem 2.4 Let A ⊂ R^{d} be a configuration of n points in general position. Let a_{1} ∈ A and R be the rank of the interior cocircuit forms.

(i) The (interior and boundary) cocircuit forms Co_{τ} for which a_{1} ∉ τ form a basis for the space of linear forms vanishing on the linear space parallel to P_{A}. Thus, R + 1 = \binom{n−1}{d}.

(ii) The vectors v_{t(Z)^{+}} − v_{t(Z)^{−}}, for the circuits Z containing a_{1}, form a basis of the linear space parallel to P_{A}. Thus, dim(P_{A}) = \binom{n−1}{d+1}.

Proof: The cocircuit forms Co_{τ} for the (d − 1)-simplices τ not containing a_{1} are linearly independent, because each simplex σ containing a_{1} appears in exactly one of them. Thus, R + 1 ≥ \binom{n−1}{d}. Likewise the vectors v_{t(Z)^{+}} − v_{t(Z)^{−}} for the circuits Z containing a_{1} are linearly independent, because each simplex σ not containing a_{1} appears in exactly one of them. Thus dim(P_{A}) ≥ \binom{n−1}{d+1}. This together with the formula dim(P_{A}) = \binom{n}{d+1} − R − 1 finishes the proof.

Proposition 2.5 If A is a configuration in general position, then aff(P_{A}) is defined by the chamber equations (3).

Proposition 2.5 is generally false for configurations in special position, because a collection of d-simplices may uniquely cover all open chambers without being a triangulation. For example, the configuration consisting of the four vertices of a quadrilateral plus the intersection of its diagonals has 3 triangulations (dim(P_{A}) = 2) while the chamber equations have 7 non-negative integer solutions whose convex hull is a 4-dimensional polytope. For the vertex set of the 3-cube we have calculated that dim(P_{A}) = 29 but the chamber equations define an affine space of dimension 35. Proposition 2.5 is implied by Theorem 2.2 and the following lemma, which expresses interior cocircuit forms as differences of chambers.

Lemma 2.6 Let A be a configuration in general position in R^{d}. Let C_{1} and C_{2} be two neighboring maximal chambers and τ the unique (d − 1)-simplex containing their common facet. Then

∑_{σ:C_{1}⊂conv(σ)}x_{σ} − ∑_{σ:C_{2}⊂conv(σ)}x_{σ} = Co_{τ} .

Proof: Let H be the hyperplane defined by τ, with half-spaces H^{+} ⊃ C_{1} and H^{−} ⊃ C_{2}. If σ is any d-simplex which contains C_{1}, then either σ contains C_{2} as well or σ = a ∪ τ where a ∈ H^{+} (similarly for C_{2}).

If A is in special position then more than one (d − 1)-simplex may contain the common facet of C_{1} and C_{2}. Call Ω the collection of them. In this case, with similar arguments one can prove that the formula in Lemma 2.6 has to be corrected by substituting ∑_{τ∈Ω} Co_{τ} for Co_{τ}.

Remark 2.7 Let M be the incidence matrix of the chambers and the d-simplices of A. If A is in general position then Proposition 2.5 implies that

aff(P_{A}) = {x ∈ R^{Δ(A)} : M · x = 1}.

Row and column bases of M have been studied in [1] and [2] and a formula is given for rank(M) in [2]. The formulae in Theorem 2.4 are a special case of that formula.

3 The relation between P_{A} and Q_{A}

Part (i) of Theorem 1.1 implies that the linear programming relaxation Q_{A} of P_{A} is defined by the interior cocircuit equations Co_{τ} = 0 plus an extra non-homogeneous equation satisfied on P_{A}, and the inequalities x_{σ} ≥ 0 for each simplex σ of A. Clearly P_{A} ⊂ Q_{A}. We shall examine the relationship between these two polytopes.

We call support of a point v ∈ R^{Δ(A)} (and denote it supp(v)) the collection of d-simplices σ for which v_{σ} ≠ 0.

Lemma 3.1 (i) Q_{A} is a subpolytope of the unit cube conv(x : x ∈ {0, 1}^{Δ(A)}).

(ii) Every vertex of P_{A} is also a vertex of Q_{A}.

(iii) If v is any point in Q_{A} then supp(v) covers conv(A), i.e.,

⋃_{σ:σ∈supp(v)} conv(σ) = conv(A).

(iv) A vertex v of Q_{A} is a vertex of P_{A} if and only if its support contains a triangulation.

Proof: The chamber equations (3) are valid for Q_{A}, and they imply part (iii). Also, since every x_{σ} appears in at least one of them, the non-negativity constraints imply x_{σ} ≤ 1 for all σ. This proves part (i) which, in turn, implies part (ii). The onlyif-direction of (iv) is obvious. For the if-direction, suppose first that supp(v) is the support of a triangulation T. Then the chamber equations imply that v is the incidence vector of T, hence is a vertex of P_{A}. If supp(v) strictly contains a triangulation T then it cannot be a vertex of Q_{A} because v_{ε} := \frac{v−εv_{T}}{1−ε} is still a point in Q_{A}, for a sufficiently small positive ε. But then v = (1 − ε)v_{ε} + εv_{T} is not a vertex of Q_{A}.

Theorem 3.2 Every integral point of Q_{A} is the incidence vector of a triangulation of A; i.e., P_{A} is the integral hull of Q_{A}.

Proof: Let v be an integral point of Q_{A}. By Lemma 3.1 (iii) we only need to prove that any two simplices in supp(v) intersect properly. Suppose this is not the case for two simplices σ_{1} and σ_{2} in supp(v), i.e.:

conv(σ_{1} ∩ σ_{2}) ≠ conv(σ_{1}) ∩ conv(σ_{2}).

Take a point a in (conv(σ_{1}) ∩ conv(σ_{2}))\conv(σ_{1} ∩ σ_{2}). Then the minimal face (subset) F of σ_{1} with a ∈ conv(F) is not a face of σ_{2}. For each simplex σ of supp(v) having F as a face, consider the convex polyhedral cone

c(σ) := a + pos(conv(σ) − a) = { λp + (1 − λ)a : p ∈ conv(σ), λ ≥ 0 }.

Note that the facets of c(σ) are in 1-to-1 correspondence with the facets of σ which contain F. We claim that conv(A) is contained in the union of such cones. Suppose a point b of conv(A) lies outside their union. Then b “sees” a facet of some cone c(σ), where σ ∈ supp(v). Let τ be the corresponding facet of σ, which contains F. By the choice of τ, there is no d-simplex in supp(v) having τ as a facet and lying in the half-space containing b. This violates the interior cocircuit equation Co_{τ} (v) = 0, since v ≥ 0. Therefore an open neighborhood of a in conv(A) is covered by those simplices in supp(v) which have F as a face. The interior of one of these simplices intersects the interior of conv(σ_{2}). This violates the chamber equations for v.

We next prove that the edges of P_{A} are also edges of Q_{A}. A different proof for this theorem can be derived from more general results about 0 − 1 polytopes due to Matsui and Tamura [10]. Here we present a self-contained proof in the context of triangulations.

Theorem 3.3 Let T_{1} and T_{2} be two distinct triangulations of A. The following statements are equivalent:

(i) v_{T_{1}} and v_{T_{2}} are not neighbors in Q_{A}.

(ii) v_{T_{1}} and v_{T_{2}} are not neighbors in P_{A}.

(iii) There exist two triangulations T_{3} and T_{4} of A (different from T_{1} and T_{2}) such that v_{T_{1}} + v_{T_{2}} = v_{T_{3}} + v_{T_{4}}.

(iv) There exist partitions T_{1} = R_{1} ∪ L_{1} and T_{2} = R_{2} ∪ L_{2} such that L_{1} ∪ R_{2} and R_{1} ∪ L_{2} are two other triangulations of A, different from T_{1} and T_{2}.

Proof: (iv)⇒(iii)⇒(ii)⇒(i) are obvious. We only need to show (i)⇒(iv). We define a graph G whose nodes are the d-simplices of T_{1}. Two d-simplices of T_{1} are adjacent in G if and only if they share a common facet and this facet is not a facet of any d-simplex of T_{2}. The graph G has the following property: If H is a connected component of G then the (topological) boundary of ∪_{σ∈H} conv(σ) is the union of (d − 1)-simplices which are faces of both T_{1} and T_{2}.

Next we will construct L_{1}, L_{2}, R_{1} and R_{2}. Let σ_{0} be a simplex of T_{1} which is not in T_{2}. Let L_{1} be the collection of d-simplices in the same connected component of G as σ_{0} and let R_{1} = T_{1}\L_{1}. Moreover, let |R| = ∪_{σ∈R_{1}}conv(σ) and |L| = ∪_{σ∈L_{1}}conv(σ). Finally, let L_{2} (resp. R_{2}) be the collection of d-simplices of T_{2} whose convex hull intersect the interior of |L| (resp. of |R|). By the property of G mentioned above, no simplex of T_{2} can intersect the interiors of both |L| and |R|. Thus T_{2} is the disjoint union of R_{2} and L_{2}. Also, by the same property, the simplices of L_{1} ∪ R_{2} (same for R_{1} ∪ L_{2}) intersect properly. Moreover, they cover conv(A), because their union covers conv(A) twice. We conclude that the disjoint unions L_{1} ∪ R_{2} and L_{2} ∪ R_{1} are triangulations of A. Clearly L_{1} ≠ L_{2}, because σ_{0} ∈ L_{1}\L_{2}. Let us assume that R_{1} = R_{2} and prove that then v_{T_{1}} and v_{T_{2}} are neighbors in Q_{A}. This will finish the proof of the theorem.

Let v be a point in the minimal face F of Q_{A} containing v_{T_{1}} and v_{T_{2}}. This face is defined setting all coordinates not appearing in v_{T_{1}} or v_{T_{2}} equal to zero. Thus, supp(v) ⊂ T_{1} ∪ T_{2}. The entry of v corresponding to any d-simplex in R_{1} = R_{2} equals 1, because of the chamber equations. On the other hand, for any two d-simplices σ_{1} and σ_{2} adjacent in G, the interior cocircuit equations imply v_{σ_{1}} = v_{σ_{2}}, since these two simplices are the only ones in T_{1} ∪ T_{2} having τ = σ_{1} ∩ σ_{2} as a facet. Thus, the entries of v corresponding to simplices in L_{1} have a constant value ε. With this, the chamber equations imply that the entries corresponding to simplices in L_{2} have a constant value 1 − ε. Thus, v = εv_{T_{1}} + (1 − ε)v_{T_{2}}. This implies that F is a segment, i.e., that v_{T_{1}} and v_{T_{2}} are neighbors.

The above theorem implies that any two integral vertices of Q_{A} (triangulations) are connected by a path of integral vertices. Note that it is still conceivable that we could have two triangulations of A which are not connected by bistellar flips.

4 Examples and applications

Our linear programming relaxation Q_{A} is generally not a lattice polytope. Therefore P_{A} is strictly contained in Q_{A}. In this section we will exhibit some cases where P_{A} = Q_{A} and the smallest configuration for which P_{A} ≠ Q_{A}.

Theorem 4.1 Let A ⊂ R^{d} be a configuration of n points. The equality P_{A} = Q_{A} holds in the following cases:

(i) d = 2 and all points lie on the boundary of a convex polygon.

(ii) d = 1.

(iii) n ≤ d + 3.

Proof: (i) Let v be a vertex of Q_{A}. Let S be a subset of supp(v) where all triangles in S intersect properly and cover a convex sub-polygon of conv(A). Suppose that S is maximal with these two properties. Let e be an edge of the sub-polygon covered by S. Then S is contained in one of the two half-planes defined by e. By maximality of S and the interior cocircuit equations, e must be a segment on the boundary of conv(A). This proves that S covers conv(A) and hence is a triangulation. Lemma 3.1 (iv) implies that v is a vertex of P_{A}. (ii) The proof is a minor variation of case (i). (iii) Let S = {T_{1}, …, T_{k}} be the collection of all triangulations of A. By Corollary 5.9 below, every triangulation T_{i} of A contains a simplex σ_{i} which is not contained in any other triangulation. Therefore, setting the coordinate of σ_{i} equal to zero defines a facet of P_{A} that contains every triangulation but T_{i}. Thus, P_{A} is a (k − 1)-simplex. The fact that all facets of P_{A} are defined by setting coordinates equal to zero implies that P_{A} = Q_{A}.

Example 4.2 A fractional vertex of Q_{A}. For any A with P_{A} ≠ Q_{A} we must have n ≥ d+4 ≥ 6. A minimal example is provided by the vertices 1, …, 5 of a regular pentagon plus its center 0. This configuration is in general position and has 20 triangles and 16 triangulations. Consider the vector v ∈ R^{20} with coordinates v_{{123}} = v_{{234}} = v_{{345}} = v_{{145}} = v_{{125}} = v_{{013}} = v_{{024}} = v_{{035}} = v_{{014}} = v_{{025}} = 1/2 and all other coordinates zero. It satisfies the interior and boundary cocircuit equations. Therefore v lies in Q_{A}. Since supp(v) does not contain any triangulation, P_{A} ≠ Q_{A}. This fractional point is the only vertex of Q_{A} which is not in P_{A}.

Remark 4.3 The property P_{A} = Q_{A} is neither sufficient nor necessary for a configuration A to have all triangulations regular. In Example 4.2 all triangulations are regular but P_{A} ≠ Q_{A}. For the canonical example of the planar configuration which has non-regular triangulations (six points which form two triangles with parallel edges) we still have P_{A} = Q_{A}.

Let C_{n} be the vertex set of a planar n-gon. The following proposition gives an irredundant inequality presentation of the \binom{n−1}{3}-dimensional polytope P_{C_{n}} = Q_{C_{n}}.

Proposition 4.4 For n ≥ 5 the facets of P_{C_{n}} are defined by x_{σ} = 0 where σ is a triangle with at most one of its edges lying on the boundary of C_{n}.

Proof: We call a triangle external if it has two edges on the boundary of C_{n}. We first show that, for any external triangle σ, x_{σ} = 0 does not define a facet of P_{C_{n}}. Without loss of generality we can assume σ = {1, 2, n}. Suppose that x_{σ} = 0 defines a facet of P_{C_{n}}. Then \binom{n−1}{3} affinely independent triangulations not involving σ together with a triangulation T that contains σ will affinely span aff(P_{C_{n}}). The triangulation T contains a triangle {i, 2, n} for some i ≠ 1. Since n ≥ 5 there exists another triangulation S which contains {j, 2, n} where j ≠ 1, i. But then S cannot be expressed as an affine combination of the above set of triangulations since {j, 2, n} cannot appear in any of them. This contradiction shows that an external triangle does not define a facet of Q_{C_{n}}.

For n = 5 a direct investigation shows that the five non-external triangles correspond to facets. For n > 5, suppose σ is a non-external triangle. Then there exists a vertex i such that C_{n−1} := C_{n}\i contains σ as a non-external triangle. Without loss of generality we can assume i = 1. Let τ be the external triangle {1, 2, n}. By induction, x_{σ} = 0 defines a facet of C_{n−1}. In other words, there are \binom{n−2}{3} affinely independent triangulations of C_{n−1} which do not contain σ. This set of affinely independent triangulations can be extended to triangulations of C_{n} by adding τ. Now we need to produce \binom{n−2}{2} additional affinely independent triangulations which do not contain σ: for each j and k such that 2 < j < k < n, we can construct a triangulation which contains the triangles {1, 2, j}, {1, j, k} and {1, k, n} (and hence not τ), and which does not contain σ. Similarly, for each 2 < l < n we can construct triangulations which contain \{1, 2, l\} and \{1, l, n\}. These additional \binom{n−2}{2} triangulations together with the previous ones form a set of \binom{n−1}{3} affinely independent points in P_{C_{n}}, none of them containing σ.

Remark 4.5 The argument that x_{σ} = 0 does not define a facet of Q_{C_{n}} whenever σ is an external triangle can be generalized. The “external” simplices of a point configuration A in general position are the following: if any vertex a_{i} of conv(A) is deleted, then the point configuration A\a_{i} will again be in general position. Each facet of conv(A\a_{i}) that is visible from a_{i} together with a_{i} will form a simplex σ which will not define a facet for Q_{A}. The argument is identical to the one above.

We close this section with remarks about using Q_{A} to enumerate the triangulations of A and to solve optimization problems over P_{A}. If A is in general position then, by Remark 2.7

Q_{A} = {x ∈ R_{+}^{Δ(A)} : M · x = 1} ,
P_{A} = conv{x ∈ {0, 1}^{Δ(A)} : M · x = 1}.

This means that P_{A} is a set partitioning polytope. Even if A is not in general position, by introducing extra variables for the interior (d−1)-simplices of A, P_{A} can be realized as a set partitioning polytope. This has important implications for enumeration and optimization purposes. For example, Trubin [15] shows that if P is a set partitioning polytope and Q its linear relaxation then P is quasi-integral, i.e., every edge of P is also an edge of Q. Balas and Padberg [3] and Matsui and Tamura [10] have given a characterization of adjacency between vertices of P. This leads to an algorithm for optimizing linear functionals over P using Q. Starting from an integral vertex of Q the algorithm finds the optimal solution visiting only integral vertices of Q in a fashion similar to the simplex method in linear programming. The same adjacency characterization can be used to enumerate the vertices of P as well.

Unfortunately, no implementation of the Balas-Padberg procedure is known to us. Moreover enumerating the triangulations of A using the existing vertex enumeration packages has two major drawbacks. First of all, an inequality presentation of P_{A} is either hard to get or it might involve too many constraints. Secondly if one uses Q_{A} instead of P_{A} then there is an excessive number of fractional vertices which have to be enumerated too. Our experiments using several vertex enumeration packages allowed us only to compute small examples. However the situation is more promising for optimization problems over P_{A} thanks to the efficient implementations of branch-and-bound and branch-and-cut algorithms for integer programming. Finding triangulations using minimum or maximum number of simplices, or finding a minimum/maximum cost triangulation fall into the category of these optimization problems. In order to illustrate the sizes of the problems one can attempt to solve and the efficiency of using linear and integer programming techniques over P_{A} we give the following example. Triangulating the d-dimensional cube with minimal number of simplices is important for their use in algorithms for the computation of fixed points of continuous maps [14]. This is equivalent to minimizing the functional ∑ x_{σ} over P_{A} where A is the vertex set of the d-cube. In the case of the 4-cube (d = 4, n = 16) the system defining Q_{A} has 1257 equations and 3008 variables. Using CPLEX 3.0 on a SPARC10 workstation, it takes 150 seconds to verify that the 4-cube’s minimal triangulation has 16 simplices. The size of the corresponding linear programs for the d-cube with d ≥ 5 gets too big. In this case one should formulate a smaller linear program which exploits the symmetries of the d-cube. This was done successfully for d = 5, 6 in [8].

5 Duality

In this section we extend the duality theory in [5] to cover all triangulations. Two applications are included: a short proof of Carl Lee’s result that every triangulation of a configuration of d + 3 points is regular [9] and an exponential lower bound for the number of triangulations of the cyclic polytope C_{4n−4}(4n).

Following [5], we now consider a configuration A = {a_{1}, a_{2}, …, a_{n}} of vectors spanning R^{d+1}. Thus |Δ(A)| ≤ \binom{n}{d+1} and equality holds if A is in general position. If there exists an affine hyperplane H (0 ∉ H) which intersects pos(a_{i}) for every a_{i} ∈ A, then we can consider A as a d-dimensional point configuration in H (identified with R^{d}). If this is the case A is said to be acyclic, and we are in the setting of the previous sections. For the non-acyclic case see Remark 5.2 below.

Let B = {b_{1}, b_{2}, …, b_{n}} be a spanning subset of R^{n−d−1} which is a Gale transform of A. This means that ∑_{i=1}^{n} a_{i} ⊗ b_{i} = 0 in R^{d+1} ⊗ R^{n−d−1}. In particular, M(B) is the oriented matroid dual to M(A).

Let T (A) ⊂ {0, 1}^{Δ(A)} be the set of incidence vectors of all triangulations of A and T_{reg}(A) the subset corresponding to regular triangulations. Similarly let Γ(A) ⊂ {0, 1}^{Δ(A)} be the set of all chambers of A. By the results in [5],

T_{reg}(A) = Γ(B)  and  T_{reg}(B) = Γ(A).  (5)

We identify each cocircuit form Co_{τ} of A with its coefficient vector in {0, +1, −1}^{Δ(A)}. Let Co(A) denote the collection of all cocircuit vectors Co_{τ}, where τ runs over all linearly independent d-subsets of A, and let Co_{int}(A) be the subset of interior cocircuit vectors. Recall that Co_{τ} is interior if and only if both +1 and −1 appear among the coordinates of Co_{τ}. Dually, let ρ be any spanning (d + 2)-subset of A. Then ρ contains a unique signed circuit Z = (Z_{+}, Z_{−}) of A. We define the circuit vector

Ci_{ρ} := ∑_{i∈Z_{−}} e_{ρ\i} − ∑_{j∈Z_{+}} e_{ρ\j}.

(The e_{ρ\i} are standard basis vectors in R^{Δ(A)}.) We say that Ci_{ρ} is an interior circuit vector if Z_{+} ≠ ∅ and Z_{−} ≠ ∅. Let Ci(A) denote the set of all circuit vectors and Ci_{int}(A) the subset of interior circuit vectors. A is acyclic if and only if Ci(A) = Ci_{int}(A). We fix the standard inner product ⟨ · , · ⟩ on R^{Δ(A)}. Here is our first duality theorem.

Theorem 5.1 Let A ⊂ R^{d+1} and B ⊂ R^{n−d−1} be Gale transforms of each other.

(i) Circuit and cocircuit vectors satisfy Ci(A) = Co(B) and Ci(B) = Co(A).

(ii) If A is in general position then the subspaces spanned by Ci(A) and Co(A) are orthogonal complements in R^{Δ(A)}.

Proof: Recall the following two facts from oriented matroid duality: A (d + 2)- subset of A is spanning if and only if the complementary (n − d − 2)-subset of B is linearly independent. The signed circuits of A are the signed cocircuits of B and vice versa. These two facts imply assertion (i). (ii) Let Ci_{ρ} be a circuit vector and let Co_{τ} be a cocircuit vector. If supp(Ci_{ρ}) ∩ supp(Co_{τ}) = ∅ then ⟨Co_{τ} , Ci_{ρ}⟩ = 0. Otherwise supp(Ci_{ρ}) ∩ supp(Co_{τ}) = {σ_{1}, σ_{2}} where σ_{1} = {τ, i} = ρ\j and σ_{2} = {τ, j} = ρ\i. If a_{i} and a_{j} are in different half-spaces defined by τ then {τ, i} and {τ, j} have the same sign in Ci_{ρ} since they appear in the same triangulation of ρ. If a_{i} and a_{j} are in the same half-space then {τ, i} and {τ, j} have opposite signs in Ci_{ρ} since they do not belong to the same triangulation of ρ. This shows

⟨Co_{τ} , Ci_{ρ}⟩ = 0  for all Co_{τ} ∈ Co(A) , Ci_{ρ} ∈ Ci(A).  (6)

If A is acyclic, by the proof of Theorem 2.4 we have dim(Co(A)) = \binom{n−1}{d} and dim(Ci(A)) = \binom{n−1}{d+1}. We conclude that Ci(A) and Co(A) span orthogonal complements. If A is in general position but not acyclic, then B is acyclic and the result follows from (i).

The orthogonality relation (6) need not hold for configurations A in special position. For example, let A = {a_{1}, a_{2}, …, a_{6}} be the vertex set of the regular octahedron where a_{5} and a_{6} are not connected by an edge. If we choose τ = {1, 2, 3} and ρ = {1, 2, 3, 4, 5}, then ⟨Co_{τ} , Ci_{ρ}⟩ ≠ 0.

Remark 5.2 The main results of Section 2 and 3 can be extended to vector configurations. The dimension formula given for point configurations in general position should be corrected to dim(P_{A}) = \binom{n−1}{d+1}−1 whenever A is a non-acyclic configuration in general position. This can be proved using duality.

Proposition 5.3 For every vector configuration A, the orthogonal complement of Ci(A) is contained in Co(A) and vice versa.

Proposition 5.3 can be deduced from the following theorem.

Theorem 5.4 For a vector X ∈ {0, 1}^{Δ(A)} the following are equivalent:

(a) ∀ T ∈ T_{reg}(A) ⟨X, T ⟩ = 1 and ∀ Ci_{ρ} ∈ Ci_{int}(A) ⟨X, Ci_{ρ}⟩ = 0.

(b) ∀ T ∈ T (A) ⟨X, T ⟩ = 1 and ∀ Ci_{ρ} ∈ Ci_{int}(A) ⟨X, Ci_{ρ}⟩ = 0

(c) X is the incidence vector of a triangulation of B, that is, the set of all (n−d−1)- subsets σ satisfying X_{{1,...,n}\σ} = 1 defines a triangulation of B.

Proof: The equivalence of (a) and (b) follows from aff(T_{reg}(A)) = aff(T (A)) which is a consequence of Corollary 2.4. Using Theorem 5.1 (i) and equation (5) we see that (a) is equivalent to

∀ C ∈ Γ(B) ⟨X, C⟩ = 1 and ∀ Co_{τ} ∈ Co_{int}(B) ⟨X, Co_{τ} ⟩ = 0. The 0-1-solutions X to this are the triangulations of B by Theorem 1.1.

Corollary 5.5 If A is in general position then for a vector X ∈ {0, 1}^{Δ(A)} the following are equivalent:

(a) ⟨X, T ⟩ = 1 for all T ∈ T_{reg}(A) .

(b) ⟨X, T ⟩ = 1 for all T ∈ T (A) .

(c) X is the incidence vector of a triangulation of B.

The chambers of A constitute a (generally proper) subset of the vectors X ⊂ {0, 1}^{Δ(A)} characterized by the three equivalent conditions in Theorem 5.4. We propose the following interpretation for the remaining solutions:

Definition 5.6 The solutions X ∈ {0, 1}^{Δ(A)} to the system (a) in Theorem 5.4, viewed as collections of (d + 1)-subsets in A, are called the virtual chambers of A. Writing Γ_{virt}(·) for the set of virtual chambers, we have

T (A) = Γ_{virt}(B)  and  T (B) = Γ_{virt}(A).  (7)

Remark 5.7 There are two kinds of virtual chambers in Γ_{virt}(B) \ Γ(B): the first kind of these can become real chambers in a different realization of M(B). These correspond to the triangulations of A which are regular in some other realization of M(A). The second kind, the “truly” virtual chambers, will never show up as real chambers and thus they correspond to non-regular triangulations which never become regular. An example of the second kind can be found in Proposition 9.6.4 in [6].

We now present two applications of our duality results.

Proposition 5.8 (Carl Lee, [9]) If A is a vector configuration in R^{d+1} with |A| ≤ d + 3 then every triangulation of A is regular.

Figure 1: A Gale diagram of C_{12}(8)

Proof: If |A| = d + 1, there is a trivial triangulation which is regular. The case |A| = d+2 is still very easy, since the linear transform B of A is one-dimensional. Let us assume that |A| = d + 3. Then B is two-dimensional and its simplices are pairs of independent vectors. Let C be a virtual chamber of B and let {b_{1}, b_{2}} be a simplex in the support of C. We have the following:

(a) if b′ ∈ B is such that pos(b_{1}, b_{2}) ⊂ pos(b_{1}, b′) then {b_{1}, b′} is in the support of C.

(b) if b′ ∈ B lies in pos(b_{1}, b_{2}), then exactly one of {b_{1}, b′} and {b′, b_{2}} is in the support of C.

Both properties follow from ∀Ci_{ρ} ∈ Ci_{int}(B), ⟨C, Ci_{ρ}⟩ = 0. Moreover, since ∀T ∈ T (B), ⟨C, T ⟩ = 1, a simplex {b_{i}, b_{j}} where pos(b_{i}, b_{j}) ⊈ pos(b_{1}, b_{2}) cannot be in C. From these we conclude that there is a unique minimal simplex lying in C. This implies that C is a real chamber.

Corollary 5.9 If A is a vector configuration in R^{d+1} with |A| ≤ d + 3, then every triangulation of A contains a simplex which is not used in any other triangulation of A.

Proof: For |A| = d + 1 and for |A| = d + 2 the statement is again trivial. For the case |A| = d + 3, the minimal simplex of C in the proof of the Theorem 5.8 is such a simplex.

The triangulations of all cyclic polytopes C_{d}(n) are known to be connected by bistellar flips [11]. We close the paper with a result about the abundance of nonregular triangulations of C_{d}(n).

Proposition 5.10 If A is the vertex set of C_{4n−4}(4n), then A has O(n^{4}) regular triangulations and has at least 2^{n} triangulations.

Figure 2: A perturbation that creates a chamber

Proof: The fact that A has O(n^{4}) regular triangulations was established in [4], Theorem 5.7 (note that their “d” corresponds to the “d + 1” in our notation). A Gale transform B = {b_{1}, b_{2}, …, b_{4n}} of A can be depicted as a (4n)-gon under taking the antipodals of {b_{2}, b_{4}, …, b_{4n}} (see Figure 1 and also compare with Figure 1 in [5]). That configuration can be assumed to be a regular 4n-gon, in particular, the sub-configuration {b_{1}, b_{3}, …, b_{4n−1}} is a regular 2n-gon. Hence, the cones pos(b_{i}, b_{i+2n}), 1 ≤ i ≤ 2n − 1 and i odd, intersect in a half-line L. Now by perturbing the vertices of this 2n-gon, we can create 2^{n} different chambers which correspond to 2^{n} distinct triangulations of A (see Figure 2). These chambers are virtual chambers of A, because the small perturbation does not change the oriented matroid. This shows that C_{4n−4}(4n) has at least 2^{n} non-regular triangulations. All of them become regular for some point configuration combinatorially equivalent to A. Acknowledgments: We thank Victor Reiner for helpful remarks and questions. We are also grateful to David Avis for his help on using his vertex enumeration package RS.

References

[1] T.V. Alekseyevskaya, I.M. Gel’fand and A. Zelevinsky Arrangements of real hyperplanes and the associated partition function, Soviet Math. Doklady 36, (1988), 589-593.

[2] T.V. Alekseyevskaya Combinatorial bases in systems of simplices and chambers, to appear on FPSAC 94, International Conference on Formal Power Series and Algebraic Combinatorics, 1994.

[3] E. Balas and M. Padberg On the set-covering problem: II. An algorithm for set partitioning, Operations Research, 23 (1975), 1152-1161.

[4] L. Billera, P. Filliman and B. Sturmfels Constructions and complexity of secondary polytopes, Advances in Math. 83 (1990), 155-179.

[5] L. Billera, I.M. Gel’fand and B. Sturmfels Duality and minors of secondary polyhedra, J. Combinatorial Theory, Ser. B 57 (1993), 258-268.

[6] A. Björner, M. Las Vergnas, B. Sturmfels, N. White and G. Ziegler Oriented Matroids, Cambridge University Press, 1992.

[7] I.M. Gel’fand, M. Kapranov, A. Zelevinsky Multidimensional Determinants, Discriminants and Resultants, Birkhäuser, Boston, 1994.

[8] R.B. Hughes Minimum-cardinality triangulations of the d-cube for d = 5 and d = 6, Discrete Mathematics 118 (1993), 75-118.

[9] C.W. Lee Regular triangulations of convex polytopes, in: Applied Geometry and Discrete Mathematics-The Victor Klee Festschrift, (P. Gritzmann and B. Sturmfels eds.) Dimacs Series in Discrete Math. and Theoretical Comp. Science 4 (1991), 443-456.

[10] T. Matsui and S. Tamura Adjacency on combinatorial polyhedra, Discrete Applied Math. 56 (1995), 311-321.

[11] J. Rambau Triangulations of cyclic polytopes and higher Bruhat orders, Report No. 496 (1996), TU Berlin,

ftp.math.tu-berlin.de/pub/Preprints/combi/Report-496-1996.ps.Z.

[12] J. Rambau and G. Ziegler Projections of polytopes and the generalized Baues conjecture, Discrete Comput. Geometry, to appear.

[13] E. Schönhardt Über die Zerlegung von Dreieckspolyedern in Tetraeder, Mathematische Annalen, 98 (1928), 309-312.

[14] M.J. Todd The Computation of Fixed Points and Applications, Springer-Verlag, Berlin, 1976.

[15] V.A. Trubin On a method of solution of integer linear programming problems of a special kind, Soviet Math. Doklady, 10 (1969), 1544-1546.

[16] G. Ziegler Lectures on Polytopes, Springer-Verlag, New York, 1994.

Jesús A. de Loera

The Geometry Center and School of Mathematics University of Minnesota Minneapolis, MN 55455, USA deloera@geom.umn.edu Serkan Hoşten School of Operations Research Cornell University Ithaca, NY 14853, USA hosten@orie.cornell.edu

Fransisco Santos

Departamento de Matemáticas Estadística y Computación Universidad de Cantabria Santander, E-39071, Spain santos@matsun1.unican.es Bernd Sturmfels Department of Mathematics University of California Berkeley, CA 94720, USA bernd@math.berkeley.edu 120

Documenta Mathematica 1 (1996)