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

We present a new class of metrics on , which we call the scaled
embedding-generated (SEG) metric. These metrics are defined with the help of
a smooth one-to-one embedding of into 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 , 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 , 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.