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 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).