Delaunay Triangulations of Points on Circles - Archive ouverte HAL Access content directly
Preprints, Working Papers, ... Year :

Delaunay Triangulations of Points on Circles

(1) , (1) , (2) , (2)
1
2

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.
Fichier principal
Vignette du fichier
circleDelaunay-arXiv.pdf (599.7 Ko) Télécharger le fichier
Vignette du fichier
vignette.png (54.85 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Format : Figure, Image
Loading...

Dates and versions

hal-01780607 , version 1 (27-04-2018)

Identifiers

Cite

Vincent Despré, Olivier Devillers, Hugo Parlier, Jean-Marc Schlenker. Delaunay Triangulations of Points on Circles. 2018. ⟨hal-01780607⟩
237 View
45 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More