Voronoi diagrams from distance graphs

M. Kapl, F. Aurenhammer, and B. Jüttler


We present a new type of Voronoi diagram in $R^{2}$ that respects the anisotropy exerted on the plane by a given distance graph. It is based on a metric obtained by smoothly and injectively embedding $R^{2}$ into $R^{m}$, and a scalar-valued function for re-scaling the distances. A spline representation of the embedding surface is constructed with the Gauß-Newton algorithm, which approximates the given distance graph in the sense of least squares. The graph is required to satisfy the generalized polygon inequality. We explain a simple method to compute the Voronoi diagrams for such metrics, and give conditions under which Voronoi cells stay connected. Several examples of diagrams resulting from different metrics are presented.

Reference: M. Kapl, F. Aurenhammer, and B. Jüttler. Voronoi diagrams from distance graphs. In Proc. $29^{th}$ European Workshop on Computational Geometry EuroCG 2013, pages 185-188, Braunschweig, Germany, 2013.