Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Delaunay Triangulations of Points on Circles

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.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download
Contributor : Olivier Devillers Connect in order to contact the contributor
Submitted on : Friday, April 27, 2018 - 4:37:00 PM
Last modification on : Saturday, October 16, 2021 - 11:26:10 AM


Files produced by the author(s)


  • HAL Id : hal-01780607, version 1
  • ARXIV : 1803.11436



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



Record views


Files downloads