HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information

Enumerating Triangulations of Convex Polytopes

Abstract : A triangulation of a finite point set A in $\mathbb{R}^d$ is a geometric simplicial complex which covers the convex hull of $A$ and whose vertices are points of $A$. We study the graph of triangulations whose vertices represent the triangulations and whose edges represent geometric bistellar flips. The main result of this paper is that the graph of triangulations in three dimensions is connected when the points of $A$ are in convex position. We introduce a tree of triangulations and present an algorithm for enumerating triangulations in $O(log log n)$ time per triangulation.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [15 references]

https://hal.inria.fr/hal-01182975
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Thursday, August 6, 2015 - 12:02:12 PM
Last modification on : Friday, December 18, 2020 - 5:30:03 PM
Long-term archiving on: : Wednesday, April 26, 2017 - 10:11:57 AM

File

dmAA0107.pdf
Publisher files allowed on an open archive

Citation

Sergei Bespamyatnikh. Enumerating Triangulations of Convex Polytopes. Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001, 2001, Paris, France. pp.111-122, ⟨10.46298/dmtcs.2295⟩. ⟨hal-01182975⟩

Record views