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
p_{i} or a
generator set of points P = {p_{i}, . . . , p_{n}}. 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) = {{p_{11}, . . . p_{1k}},
. . . , {p_{l1} , . . . p_{lk}}}, p_{ij }
P,*
l *= _{n}C_{k}.

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

Vor_{k}(S) =
V (T), T
S, | T | = k

In this notation, the ordinary Voronoi diagram is just
Vor_{1}(S).

**Theorem **
The order-k Voronoi diagram of an n point set is obtained in
time O(*k*^{2} n log n).