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.


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:
           Convex Distance Function

Google Scholar finds 42 papers post-2000 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$ – Misha Feb 21 '13 at 16:23
  • $\begingroup$ @Misha: Not coincidentally, Rolf Klein was Lihong Ma's thesis supervisor! :-) Thanks for the references. $\endgroup$ – Joseph O'Rourke Feb 21 '13 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$ – domotorp Feb 22 '13 at 16:12
  • $\begingroup$ I managed to access the book, it does not even mention Delaunay triangulations. $\endgroup$ – domotorp Feb 27 '13 at 13:55
  • $\begingroup$ It seems that I have misunderstood the definition of reference-request, thank you for your answer. $\endgroup$ – domotorp Mar 1 '13 at 16:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.