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.

$\begingroup$ Crossposted on CSTheory: cstheory.stackexchange.com/questions/16661/… $\endgroup$– domotorpFeb 27, 2013 at 13:56
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 post2000 that cite this dissertation.

4$\begingroup$ See also R.Klein's book "Concrete and abstract Voronoi diagrams" as well as N.M.Le's papers from 1990s on this subject. $\endgroup$– MishaFeb 21, 2013 at 16:23

$\begingroup$ @Misha: Not coincidentally, Rolf Klein was Lihong Ma's thesis supervisor! :) Thanks for the references. $\endgroup$ Feb 21, 2013 at 16:33

$\begingroup$ 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/… $\endgroup$– domotorpFeb 22, 2013 at 16:12

$\begingroup$ I managed to access the book, it does not even mention Delaunay triangulations. $\endgroup$– domotorpFeb 27, 2013 at 13:55

$\begingroup$ It seems that I have misunderstood the definition of referencerequest, thank you for your answer. $\endgroup$– domotorpMar 1, 2013 at 16:10