# 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.

-
Cross-posted on CSTheory: cstheory.stackexchange.com/questions/16661/… –  domotorp Feb 27 '13 at 13:56

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. (CiteSeer link)

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

Google Scholar finds 22 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