[Math] Delaunay triangulations and convex hulls

convex-geometrydiscrete geometrygraph theorymg.metric-geometryreference-request

This is a reference request.

I have the impression that those who work in computational geometry are accustomed to the following. You have some locally finite set of sites in $\mathbb{R}^n$ and you want to think about their Delaunay triangulation, and then you look at the map
$$
(x_1,\ldots,x_n) \mapsto (x_1,\ldots,x_n,x_1^2+\cdots+x_n^2)\in\mathbb{R}^{n+1},
$$
and the Delaunay triangulation then corresponds to the "lower convex hull". For suitably bounded sets of sites (e.g. all lying in some particular half-plane, or—more drastic still—actually bounded in the sense of having finite diameter) there's also an "upper convex hull" that sometimes gets some attention.

But there's a simpler correspondence that might be less well-known, if vague impressions from talking to a few people are right. Suppose you have a finite set of sites on the sphere $(x_1^2+\cdots+x_n^2=1)$ (not $\le1$) and you measure distances between sites along great circles. Voronoi cells are parts of the surface bounded by great circles; the Delaunay triangulation connects sites whose Voronoi cells touch each other. The statement is this:

The facets of the convex hull of the set of sites are precisely the Delaunay triangles. (Or Delaunay simplices if you want to go to higher dimensions.)

There's no occasion to distinguish between "upper" and "lower". I think this might be counterintuitive to those accustomed to "upper" and "lower". Suppose two sites in a bounded set of sites in the plane are connected by a line that's on the boundary of the "upper" convex hull. Then we suddenly realize that the world is not flat; what we thought was a flat plane is a small region of an immense sphere. Those two Voronoi cells that we had thought were unbounded and not neighbors actually touch each other in an antipodal region. Hence no upper/lower distinction, and we have a simpler proposition than one that involves those.

Here's the question: Is the proposition in bold above found somewhere in the literature in this simple form, with neither any distinction between "upper" and "lower" nor between "nearest"- and "farthest"-point diagrams?

In an earlier thread at n-dimensional voronoi diagram, Joseph O'Rourke pointed out a paper by Kevin Q. Brown that works with spheres rather than paraboloids and deals with the convex hull, but still works with "nearest" and "farthest" because he's ultimately concerned with the plane, not with the sphere.

Best Answer

It certainly appears in this survey paper by Franz Aurenhammer (see Figure 11). The paper cites Klee, On the complexity of d-dimensional Voronoi diagrams as well as K.Q. Brown's Ph.D. thesis, Geometric transforms for fast geometric algorithms.

Related Question