3
$\begingroup$

Commonly the assumption that is made on point sets that shall be Delaunay-triangulated is that no three are collinear and no four are cocircular.

Those assumptions are however too restrictive: if the pointset consists of the corners of a regular n-gon plus the center of the circle on which those corners lie, then the Delaunay triangulation is unambiguous and not degenerate in any sense.

The correct condition would rather be that no four points are cocircular on a circle with empty interior.

Questions:

  • have the original conditions regarding cocircularity been formulated correctly and only later has the emptyness condition been brushed under the carpet?
  • What are examples of publications that make the correct assumptions when discussing the Delaunay triangulation?
Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

I think it is well-understood that "no four points cocircular" avoids Delaunay triangulation degeneracies. It is also well-understood that one can have four cocircular points that don't cause any degeneracies, as in your example.

Perhaps this paper addresses your concern. The authors explicitly define the tolerance of the Delaunay triangulation of a point set as the smallest perturbation of the points that causes a diagonal flip (and they justify this definition). This naturally leads to studying the annulus illustrated below.

Abellanas, Manuel, Ferran Hurtado, and Pedro A. Ramos. "Structural tolerance and Delaunay triangulation." Information Processing Letters 71, no. 5-6 (1999): 221-227. PDF download.

          enter image description here

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .