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₁₁, . . . p_1k}, . . . , {p_l1 , . . . p_lk}}, p_ij P, l = _nC_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₁(S).

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