Using Scaled Embedded Distances to Generate Metrics for ${R}^2$

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


We present a new class of metrics on $R^{2}$, which we call the scaled embedding-generated (SEG) metric. These metrics are defined with the help of a smooth one-to-one embedding of $R^{2}$ into $R^{m}$ and an additional scalar-valued function which is used to re-scale the distances. We describe a possible construction of an SEG metric which is based on the Gauß-Newton algorithm. More precisely, we show how to generate a spline embedding, which approximates a given distance graph on a finite set of points in $R^{2}$, in the sense of least squares. Distances are required to satisfy the generalized polygon inequality. The framework is used to define a new type of Voronoi diagram in $R^{2}$, which is possibly anisotropic as it allows for different distance functions for the sites. We explain a simple method to compute such Voronoi diagrams. Several examples of diagrams resulting from different SEG metrics are presented.

Reference: M. Kapl, F. Aurenhammer, and B. Jüttler. Using scaled embedded distances to generate metrics for ${R}^2$. In Proc. $14^{th}$ IMA Conference on Mathematics of Surfaces, Birmingham, England, 2013.