Enumerating Triangulations of Convex Polytopes
Bespamyatnikh, Sergei
HAL, hal-01182975 / Harvested from HAL
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.
Publié le : 2001-07-04
Classification:  polytope,  bistellar flip,  triangulation,  enumeration,  [INFO]Computer Science [cs],  [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG],  [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],  [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
@article{hal-01182975,
     author = {Bespamyatnikh, Sergei},
     title = {Enumerating Triangulations of Convex Polytopes},
     journal = {HAL},
     volume = {2001},
     number = {0},
     year = {2001},
     language = {en},
     url = {http://dml.mathdoc.fr/item/hal-01182975}
}
Bespamyatnikh, Sergei. Enumerating Triangulations of Convex Polytopes. HAL, Tome 2001 (2001) no. 0, . http://gdmltest.u-ga.fr/item/hal-01182975/