Isolated edges in hyperbolic Delaunay triangulation

85 Views Asked by At

I have played with the C++ library CGAL to do some hyperbolic Delaunay triangulations. Sometimes (often) the triangulation has some isolated edges, as in this example:

enter image description here

Is it theoretically normal to get such edges? I googled but found nothing. It is said in the CGAL documentation that hyperbolic Delaunay triangulations are connected. If we consider that such edges belong to the triangulation then it is clearly not connected.

2

There are 2 best solutions below

6
On

What you call an "isolated edge" is simply an edge which is not incident to any 2-dimensional face (such an edge is called a "facet"). To see that such edges can exist, consider a finite subset of $H^2$ consisting of two distinct points. The corresponding Delaunay triangulation will consist of a single edge. More generally, consider a finite subset of $H^2$ contained in a single geodesic. Then every edge of the corresponding Delaunay triangulation will be "isolated." If you still do not liкe this example, then perturb it slightly: If the perturbation is small enough then every edge is still "isolated."

0
On

The answer is given in the CGAL documentation. As noted by Moishe Kohan, the "isolated" edges can appear for example when the set of points consist of three points aligned on a hyperbolic line. But I said that these isolated edges often appear; I forgot to say that I took the points at random, and getting aligned random points do not often occur. Moreover this is not the situation of the picture I posted.

The reason is that the authors of CGAL consider that a triangle such as the shaded one below is not hyperbolic, because its circumcircle is not contained in the Poincaré disk:

enter image description here

And so CGAL discards such triangles from the Delaunay triangulation. I said to a CGAL author that this choice surprises me because mathematically speaking, this triangle is not less hyperbolic that another one. She replies that this is not about hyperbolicity, but about the Delaunay property (so the documentation is not very clear about this point).