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$
$\endgroup$
1
-
$\begingroup$ Cross-posted on CSTheory: cstheory.stackexchange.com/questions/16661/… $\endgroup$– domotorpCommented Feb 27, 2013 at 13:56
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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 post-2000 that cite this dissertation.
answered Feb 21, 2013 at 15:55
-
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$– MishaCommented Feb 21, 2013 at 16:23
-
$\begingroup$ @Misha: Not coincidentally, Rolf Klein was Lihong Ma's thesis supervisor! :-) Thanks for the references. $\endgroup$ Commented 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$– domotorpCommented Feb 22, 2013 at 16:12
-
$\begingroup$ I managed to access the book, it does not even mention Delaunay triangulations. $\endgroup$– domotorpCommented Feb 27, 2013 at 13:55
-
$\begingroup$ It seems that I have misunderstood the definition of reference-request, thank you for your answer. $\endgroup$– domotorpCommented Mar 1, 2013 at 16:10