Consider a set of areas, A = {A₁, A₂, . . . , A_n} in R² where 1≤ n ≤ ∞.

Assumptions

1. Area A_i is a connected closed set.
2. Areas do not overlap each other, i.e.,
               A_i ∩ A_j = φ, i ≠ j,  i,j I_n .
3. An Area A_i is not necessarily Convex.
4. An Area A_i may have holes in which another area may exist.

Under these assumptions, a distance from a point to an area A_i is define as the shortest distance from p to A_i, i.e.,

d_s (p, A_i) = min_xi  {|| x-x_i || : x_i A_i}

where x and x_i are the location vectors of p and p_i, respectively. With this distance, we define the set of area of voronoi region associated with A_i by 

V(A_i) = {p : d_s(p, A_i) ≤ d_s(p, A_j), j ≠ i,   i, j I_n}

Using above definitions, a set of the area Voronoi regions is V(A) = {V(A₁), V(A₂), . . . , V(A_n)}, the area Voronoi diagram generated by the generator set A.

Mathematically, an area includes a line and a line includes a point. Thus the area Voronoi diagram includes the line Voronoi diagram. Thus, we can regard the area Voronoi diagram as a generalization of the line Voronoi diagram as well the ordinary Voronoi diagram.

Outline of an Algorithm

1. Construct the live Voronoi diagram with L(A).
2. Delete the Superfluous edges.
   1. Remaining edges form the area Voronoi diagram.

Application

Area Voronoi diagram are useful for robot path planning. The problem is to find a path, if it exists, on which a polygon representing a robot can move with colliding with obstacles A₁, A₂, . . . , A_n.

Reference

• C. O'Dunlaing, M. Sharir and C. K. Yap, Generalized Voronoi diagrams for movind a ladder-topological Analysis, Communications on Pure and Applied Mathematics (1986) 39(4), 423-483.
• D. Leven and M. Sharir, Planning a purely translational motion for a convex object in two-dimensional space using generalized Voronoi diagrams, Discrete and Computational Geometry 2(1987), 9-31.
• J. Canny and B. Donald, Simplified voronoi diagram, Discrete and Computational Geometry 3(1988), 219-236.