Delaunay triangulation for datasets with four or more co-circular points

I am working on a library that requires subdivision of polygons into triangles. The polygons are divided into triangles by (more or less) random points that are inside them. In general, the approach is to perform the Delaunay triangulation on a set of those points. This works very well, however sometimes I get intersecting triangles in my outcome. This case happens when I have more than three co-circular points. For the Delaunay triangulation I am using simple Watson's algorithm. My questions are:

1. what to do in case of four or more co-circular points. None of the CG books I've read does not mention about handling it. Just that it is some special case.

2. Are there other triangulations (similar to Delaunay - I cannot insert any additional points) I could potentially use.

• My hack has been to displace the points slightly so that they non longer meet the co-circularity condition. Jan 29, 2018 at 21:25

You can use exact predicates to detect co-circular points, and use symbolic perturbation to consistently decide which triangles to generate.

Regarding exact predicates:

• If your point coordinates are integers, then it is easier, and you can use Hadamar's inequality to determine the range of valid coordinates for which the values computed by the predicates will not overflow.
• If you use floating-point coordinates, then it is more tricky to implement. You can use either an arbitrary precision library (such as MPFR) or arithmetic expansions (as suggested by Shewchuk [1], see also his 'triangle' software)

Regarding symbolic perturbation:

Whenever the predicates answers 'right on the circle', you need to consistently disambiguate. One way to do that is explained in the 'SOS' article [2]. Basically, in a certain sense, the idea is to consider the Voronoi diagram as the limit of a power diagram with different weights for the points that tend to 0 with different speeds, and consider the first non-zero coefficient in a Taylor development of the so-parameterized predicate.

Note on efficiency:

To detect the cases where the answer can be easily/quickly determined, you can use arithmetic filters, as suggested in [3] (this has dramatic impact on the performances).

More references (my own stuff)

All these algorithms are implemented in my geogram library [4], see my associated publication [5].

• [1] Jonathan Richard Shewchuk, Robust Adaptive Precision Floating Point Geometric Predicates, SoCG, 1996

• [2] Edelsbrunner and Mucke, Simulation of Simplicity, ACM Trans. Graph., 1990

• [3] Meyer and Pion, FPG: a code generator for fast and certified geometric predicates, Real Number and Computers, 2008

• [5] The Predicates Construction Kit: https://hal.inria.fr/hal-01225202