# Delaunay triangulations and convex hulls

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.

-

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.

-
Interesting. He attributes the idea to Kevin Q. Brown and his concern with the sphere is only a means to an end, and the end involves the plane rather than the sphere, just as in Brown's paper. –  Michael Hardy Jan 23 '12 at 19:44

It's known; for example, my coauthors and I used this characterization in http://arxiv.org/abs/math.MG/0611451. However, we certainly weren't the first, and I don't know the earliest reference. I think it is well known among those who think about spherical codes, and it has probably been known for a long time, but it ought to be more broadly known.

The duality between nearest and furthest does occur even in this framework, however. It amounts to the distinction between looking at outer and inner facet normals:

If $V$ is a full-dimensional, finite subset of a sphere, then the outer normal vectors for the facets of its convex hull are the holes in $V$, i.e., the points on the sphere whose nearest neighbors in $V$ are as far away as possible. The inner normal vectors are the points for which the furthest points in $V$ are as close as possible. (It's easy to verify that multiplying by $-1$ interchanges these two conditions.)

-
I see that the words "Voronoi" and "Delaunay" are not in the paper. And it's 41 pages. Specifically where is this? –  Michael Hardy Jan 23 '12 at 6:40
Sorry for the cryptic reference; in the arXiv version, it's the second paragraph on page 23. It is phrased in terms of holes, but this is equivalent to Delaunay cells. –  Henry Cohn Jan 23 '12 at 13:29
I see. The equivalence is far from obvious to one who doesn't know the language of "hole" and "codes", etc. –  Michael Hardy Jan 23 '12 at 19:21

I have nothing to add to the literature question, but I thought I would include an image of the Voronoi Diagram on a sphere to illustrate that "Voronoi cells are parts of the surface bounded by great circles":

-
Did you do this in mathematica? Could you post the code here in the comments? –  Michael Hardy Jan 23 '12 at 19:45
I snatched the figure from a Mathematica demonstration project written by Maxim Rytin: demonstrations.wolfram.com/VoronoiDiagramOnASphere . –  Joseph O'Rourke Jan 23 '12 at 20:05

This paper by Bobenko and Izmestiev "Alexandrov's Theorem, Weighted Delaunay Triangulations, and Mixed Volumes" is based upon a generalization of this observation.

One reason that this convex-hull characterization may seem obscure is that it really only applies to points on the sphere. The paragraph in the OP that begins "There is no reason ..." is misleading because it implies that the planar Delaunay triangulation can be characterized in this way. The lower envelope of the convex hull of the traditional lifting (to a paraboloid) gives exactly the combinatorics of the planar DT. However, going to a sphere, by stereographic projection, say, is only going to work if the radius of the sphere is "big enough". For a fixed number of points n, there will be no upper bound on the radius that is big enough for all point sets of size n.

The Delaunay triangulation is brittle, and unless unusual demands on the vertex configurations are made, the combinatorial structure can change with an arbitrarily small perturbation of the metric. I.e., the point set can be arbitrarily close to being degenerate.

-