# 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 :
Type de document :
Communication dans un congrès
Cori, Robert and Mazoyer, Jacques and Morvan, Michel and Mosseri, Rémy. Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001, 2001, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AA, Discrete Models: Combinatorics, Computation, and Geometry (DM-CCG 2001), pp.111-122, 2001, DMTCS Proceedings
Domaine :

Littérature citée [15 références]

https://hal.inria.fr/hal-01182975
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 6 août 2015 - 12:02:12
Dernière modification le : mardi 7 mars 2017 - 15:00:11
Document(s) archivé(s) le : mercredi 26 avril 2017 - 10:11:57

### Fichier

dmAA0107.pdf
Fichiers éditeurs autorisés sur une archive ouverte

### Identifiants

• HAL Id : hal-01182975, version 1

### Citation

Sergei Bespamyatnikh. Enumerating Triangulations of Convex Polytopes. Cori, Robert and Mazoyer, Jacques and Morvan, Michel and Mosseri, Rémy. Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001, 2001, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AA, Discrete Models: Combinatorics, Computation, and Geometry (DM-CCG 2001), pp.111-122, 2001, DMTCS Proceedings. 〈hal-01182975〉

### Métriques

Consultations de la notice

## 197

Téléchargements de fichiers