Voronoi diagrams based on convex distance functions

We present an “expanding waves” view of Voronoi diagrams that allows such diagrams to be defined for very general metrics and for distance measures that do not qualify as metrics. If a pebble is dropped into a still pond, circular waves move out from the point of impact. If n pebbles are dropped simultaneously, the places where wave fronts meet define the Voronoi diagram on the n points of impact.

The Voronoi diagram for any normed metric, including the L_p metrics, can be obtained by changing the shape of the wave front from a circle to the shape of the “circle” in that metric. (For example, the “circle” in the L₁ metric is diamond shaped.) For any convex wave shape there is a corresponding convex distance function. If the shape is not symmetric about its center (a triangle, for example) then the resulting distance function is not a metric, although it can still be used to define a Voronoi diagram.

Like Voronoi diagrams based on the Euclidean metric, the Voronoi diagrams based on other normed metrics can be used to solve various closest-point problems (all-nearest-neighbors, minimum spanning trees, etc.). Some of these problems also make sense under convex distance functions which are not metrics. In particular, the “largest empty circle” problem becomes the “largest empty convex shape” problem, and “motion planning for a disc” becomes “motion planning for a convex shape”. These problems can both be solved quickly given the Voronoi diagram. We present an asymptotically optimal algorithm for computing Voronoi diagrams based on convex distance functions.