Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Theory of Combinatorial Algorithms
Prof. Emo Welzl and Prof. Bernd Gärtner
Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Prof. Emo Welzl and Prof. Bernd Gärtner
Minimal triangulations and dissections of convex polytopes
Jesus De Loera, University of California-Davis and ETH-Zurich
In 1993 Klee and Gritzmann proposed two related natural questions:
1) QUESTION: Is it possible that by using auxiliary interior points one can triangulate a convex polytope P with fewer tetrahedra than when the set of vertices is just the vertex set of P?
2) A dissection of a convex d-polytope is collection of d-simplices with disjoint interiors whose union is the whole polytope. Unlike triangulations, simplices may intersect in sets other than common faces (i.e not a simplicial complex).
QUESTION: Is it possible that a minimal dissection is smaller than the minimal triangulation of the polytope?
In this talk we show a family of 3-dimensional convex polytopes with this property and its many interesting consequences. This is joint work with A. Below, U. Brehm, J. Richter-Gebert.
Back
