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 1


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, 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$
    – domotorp
    Feb 22, 2013 at 16:12
  • $\begingroup$ I managed to access the book, it does not even mention Delaunay triangulations. $\endgroup$
    – domotorp
    Feb 27, 2013 at 13:55
  • $\begingroup$ It seems that I have misunderstood the definition of reference-request, thank you for your answer. $\endgroup$
    – domotorp
    Mar 1, 2013 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.