SORTING HELPS FOR VORONOI DIAGRAMS

It is well known that, using standard models of computation, Omega (n log n) time is required to build a Voronoi diagram for n point sites. This follows from the fact that a Voronoi diagram algorithm can be use d to sort. However, if the sites are sorted before we start, can the V oronoi diagram be built any faster? We show that for certain interesti ng, although nonstandard, types of Voronoi diagrams, sorting helps. Th ese nonstandard types of Voronoi diagrams use a convex distance functi on instead of the standard Euclidean distance. A convex distance funct ion exists for any convex shape, but the distance functions based on p olygons (especially triangles) lead to particularly efficient Voronoi diagram algorithms. Specifically, a Voronoi diagram using a convex dis tance function based on a triangle can be built in O (n log log it) ti me after initially sorting the it sites twice. Convex distance functio ns based on other polygons require more initial sorting.