Higher Order Voronoi Diagram


Here the 'order'  means that number of points constituting a generator and 'higher' means more than one point. Note that 'higher' does not refer to the dimension of a space.

In the ordinary Voronoi diagram a generator is a point pi or a generator set of points P = {pi, . . . , pn}. In this section that extends a single point to set of points. We consider the family of generalized Voronoi diagrams generated by a set of size-k subsets of P.


A(k)(P) = {{p11, . . . p1k}, . . . , {pl1 , . . . plk}}, pij in P, l = nCk.


This family is known as 'higher-order' Voronoi diagram.


Instead of working with the Voronoi polygon associated with a single point, we can speak of the generalized Voronoi polygon V(T) of a subset T of points [Shamos-Holy (1975)], defined by


V(T) = {p: v T w S - T, d(p, v) < d(p, w)}


That is , V(T) is the locus of points p such that each point of T is nearer to p than to any point not in T.


The Voronoi diagram of order k is define as the collection of all generalized Voronoi polygons of k-subsets of S, so


Vork(S) = V (T), T S, | T | = k


In this notation, the ordinary Voronoi diagram is just Vor1(S).


Theorem    The order-k Voronoi diagram of an n point set is obtained in time O(k2 n log n).