On shape Delaunay tessellations

F. Aurenhammer and G. Paulini


Shape Delaunay tesselations are a generalization of the classical Delaunay triangulation of a finite set of points in the plane - the empty circle condition is replaced by emptiness of an arbitrary convex compact shape. We present some new and basic properties of shape Delaunay tesselations, concerning flipping, subgraph structures, and recognition.

Reference: F. Aurenhammer and G. Paulini. On shape Delaunay tessellations. Information Processing Letters, 114(535-541), 2014.