2002/04/30 by David Orden, Francisco Santos
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #math.CO
paper · pdf · doi:10.1007/s00454-003-2845-5
published as Discrete Comput. Geom., 30:4 (2003), 509-528. · 19 pages, 6 figures. Only minor changes from previous versions, some suggested by anonymous referees. Paper accepted in "Discrete and Computational Geometry"
arxiv created 2003/03/10 · openalex publication_date 2003/10/01 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let P and Q be polytopes, the first of "low" dimension and the second of "high" dimension. We show how to triangulate the product P × Q efficiently (i.e., with few simplices) starting with a given triangulation of Q. Our method has a computational part, where we need to compute an efficient triangulation of P × Δm, for a (small) natural number m of our choice. Δm denotes the m-simplex. Our procedure can be applied to obtain (asymptotically) efficient triangulations of the cube In: We decompose In = Ik × In-k, for a small k. Then we recursively assume we have obtained an efficient triangulation of the second factor and use our method to triangulate the product. The outcome is that using k=3 and m=2, we can triangulate In with O(0.816n n!) simplices, instead of the O(0.840n n!) achievable before.