# What properties does generalized Delaunay triangulation have?

Suppose that instead of the usual circle, we pick some other convex set D and make the Delaunay triangulation of a finite planar point set with respect to this set, i.e. connect two points if there is a homothet of D that contains both of them on its boundary and no points inside. If the points are in a general position such that no four fall on the boundary of a homothet of D, then we still obtain a triangulation (plus some infinite face). Can anyone provide a good reference for this statement, how should I cite it? I need it not only for smooth D but also for polygons.

## 1 Answer

Perhaps the earliest reference is this:

Chew & Drysdale. "Voronoi diagrams based on convex distance functions." 1985. (ACM link)

This more recent dissertation at the FernUniversität Hagen may be more directly useful:

Ma. "Bisectors and Voronoi Diagrams for Convex Distance Functions." 2000. (PDF download)

I extracted this figure from her thesis, p.58:

Google Scholar finds 42 papers post-2000 that cite this dissertation.

• See also R.Klein's book "Concrete and abstract Voronoi diagrams" as well as N.M.Le's papers from 1990s on this subject. – Misha Feb 21 '13 at 16:23
• @Misha: Not coincidentally, Rolf Klein was Lihong Ma's thesis supervisor! :-) Thanks for the references. – Joseph O'Rourke Feb 21 '13 at 16:33
• Thank you, I think I will cite the book, as in the dissertation the simple properties are not stated. (I hope they are in the book, since I could not access it.) Also, here is a direct link to the dissertation: fernuniversitaethagen.de/imperia/md/content/… – domotorp Feb 22 '13 at 16:12
• I managed to access the book, it does not even mention Delaunay triangulations. – domotorp Feb 27 '13 at 13:55
• It seems that I have misunderstood the definition of reference-request, thank you for your answer. – domotorp Mar 1 '13 at 16:10