### Technical Report No. 5, December 1987 - Abstract

**Rolf Klein, Derick Wood:**

*Voronoi Diagrams Based on General Metrics in the Plane*

*This report is not available in electronic form!*

Voronoi diagrams based on metrics others than the Euclidean metric
or convex distance functions have
recently received considerable interest in robotics and in computational geometry.
Since the number of relevant metrics is large
(and likely to increase, as new applications come up)
a general theory should be developed,
leading to results on the structure and on the computation
of Voronoi diagrams that hold for large *classes* of metrics, rather
than investigating each case separately.

In this paper we make the first steps in this direction.
First we propose a uniform way of *defining* the Voronoi diagram of
*n* points;
the result is always a *partition* of the plane into *n Voronoi
regions*, even if the bisectors
of two points are two-dimensional regions.
Then we present a simple axiom for metrics that guarantees
that each possible Voronoi region is *connected*.
In this case the *normalized* Voronoi diagram is a planar graph
with *n* faces
and *O(n)* edges and vertices, if the bisectors behave well.
Next we pose two additional axioms each of which ensures that all Voronoi
regions are *simply-connected*.
One of them also implies that the bisector of two sets
of points divided by suitable line, contains no loops.
Then the normalized Voronoi diagram can be computed within optimal
*O(n*log n)* steps, using the *divide-and-conquer* algorithm.
The class of metrics thereby specified does not only contain
all symmetric convex distance functions
but also many *composite* metrics like, for example,
the combination of the "grid" metric *L1* in midtown Manhattan
and the Euclidean metric in the Central Park and on the Hudson River.