ABSTRACT
We are interested in the set of all subdivisions or triangulations of a given polytope P and with a fixed finite set V of points that can be used as vertices. V must contain the vertices of P, and it may or may not contain additional points; these additional points are vertices of some, but not all, the subdivisions that we can form. This setting has interest in several contexts:
In computational geometry there is often a set of sites V and one wants to find the triangulation of V that is optimal with respect to certain criteria.
In algebraic geometry and in integer programming one is interested in triangulations of a lattice polytope P using only lattice points as vertices.
Subdivisions of some particular polytopes using only vertices of the polytope turn out to be interesting mathematical objects. For example, for a convex n-gon and for the prism over a d-simplex they are isomorphic to the face posets of two remarkable polytopes, the associahedron and the permutahedron.
Our treatment is very combinatorial. In particular, instead of regarding a subdivision as a set of polytopes we regard it as a set of subsets of V, whose convex hulls subdivide P. This may appear to be an unnecessary complication at first, but it has advantages in the long run. It also relates this chapter to Chapter 6 (oriented matroids). For more application-oriented treatments of triangulations see Chapters 27 and 29. A general reference for the topics in this chapter is [[DRS10]].