**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 into ,
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.