Voronoi diagrams from distance graphs
M. Kapl, F. Aurenhammer, and B. Jüttler
We present a new type of Voronoi diagram in
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
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
Reference: M. Kapl, F. Aurenhammer, and B. Jüttler.
Voronoi diagrams from distance graphs.
In Proc. European Workshop on Computational Geometry EuroCG
2013, pages 185-188, Braunschweig, Germany, 2013.