Check if points lie on boundary of ball / check uniqueness of a Delaunay triangulation

user_17377789 0
Viewed 93

the Wikipedia article about Delaunay Triangulations in d dimensions states as a prerequisite for uniqueness of a triangulation:

It is known that there exists a unique Delaunay triangulation for P if P is a set of points in general position; that is, the affine hull of P is d-dimensional and no set of d + 2 points in P lie on the boundary of a ball whose interior does not intersect P.

Now that I've written my own Delaunay library, I want to be able to verify the uniqueness of the triangulation given its points. Checking the dimensionality of the affine hull can be done easily by calculating the rank of the set. The second part however is way more difficult.

How can I check if d+2 points lie on the boundary of a ball not intersecting with the set and without some gigantic loop over each point? Or is there maybe an alternative way of checking the uniqueness?

I'm using Python with Numpy, however this is more of an theoretical question, thus the language doesn't matter. Thanks!

delaunay computational-geometry geometry python
2 Answers

For each a simplex of maximal dimension of your triangulation, with d+1 points, you have d+1 neighbor simplices. Two neighbor simplices share d points (forming a simplex themselves). As I do not know if you are familiar with that working in dimension d, let's have a look at dimensions 2 and 3...

  • In dimension 2, a simplex of maximal dimension is a triangle (simplex of dimension 2), and two neighbor triangles share an edge (simplex of dimension 1).
  • In dimension 3, a simplex of maximal dimension is a tetrahedron (simplex of dimension 3), and two neighbor tetrahedra share an a face that is a triangle (simplex of dimension 2).

Anyway, given a Delaunay triangulation in dimension d, if you want to check if you have a unique triangulation, iterate on simplices of dimension d-1 (triangles in 3D, or edges in 2D), and take two incident simplices (two neighbor tetrahedra in 3D, or neighbor triangles in 2D). That gives you d+2 points. As the triangulation is Delaunay, you know that the in_sphere predicate for those d+2 points has a result positive or null. If, during the iteration on simplices of dimension d, the result of all the in_sphere predicate for the d+2 points is strictly positive, then your triangulation is unique, otherwise it is degenerated and non-unique.

Have a look at the paper Efficient Exact Geometric Predicates for Delaunay Triangulations by Olivier Devillers and Sylvain Pion: the introduction gives the basics of the theory about Delaunay triangulations, and the in_sphere predicate. It also gives leads to implement the orientation and in_sphere predicates in an exact but efficient way. That might help you in your implementation of the Delaunay triangulations.

user_17285370

You have already a Delaunay triangulation i.e., there are no points inside a circumsphere. Now, e.g., for the 2D case, simply check if you can flip any edge such that it is still a Delaunay triangulation. If not, you have a unique solution. Be aware of the rounding errors of double precision arithmetic.

user_15779180
Related