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.
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
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

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

Collections

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〉

Partager

Métriques

Consultations de la notice

195

Téléchargements de fichiers

193