Delaunay triangulations and convex hulls

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.


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 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":
           VD on sphere
           Mathematica image by Maxim Rytin.