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.
removed deprecated (geometry) tag - see the tag info: http://mathoverflow.net/tags/geometry/info; if there are some other geometry-related tags which are suitable, please use some of them instead
Martin Sleziak
- 4.7k
- 4
- 35
- 40