Delaunay Triangulations of Points on Circles

Vincent Despré 1 Olivier Devillers 1 Hugo Parlier 2 Jean-Marc Schlenker 2
1 GAMBLE - Geometric Algorithms and Models Beyond the Linear and Euclidean realm
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : Delaunay triangulations of a point set in the Euclidean plane are ubiquitous in a number of computational sciences, including computational geometry. Delaunay triangulations are not well defined as soon as 4 or more points are concyclic but since it is not a generic situation, this difficulty is usually handled by using a (symbolic or explicit) perturbation. As an alternative , we propose to define a canonical triangulation for a set of concyclic points by using a max-min angle characterization of Delaunay triangulations. This point of view leads to a well defined and unique triangulation as long as there are no symmetric quadruples of points. This unique triangulation can be computed in quasi-linear time by a very simple algorithm.
Type de document :
Pré-publication, Document de travail
2018
Liste complète des métadonnées

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


https://hal.inria.fr/hal-01780607
Contributeur : Olivier Devillers <>
Soumis le : vendredi 27 avril 2018 - 16:37:00
Dernière modification le : samedi 28 avril 2018 - 01:25:34

Fichiers

circleDelaunay-arXiv.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Vincent Despré, Olivier Devillers, Hugo Parlier, Jean-Marc Schlenker. Delaunay Triangulations of Points on Circles. 2018. 〈hal-01780607〉

Partager

Métriques

Consultations de la notice

170

Téléchargements de fichiers

49