MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Cross-posted on CSTheory:… – domotorp Feb 27 '13 at 13:56
up vote 3 down vote accepted

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

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

share|cite|improve this answer
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:… – 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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