Area of Voronoi Region


Consider a set of areas, A = {A1, A2, . . . , An} in R2 where 1≤ n ≤ ∞.


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


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


ds (p, Ai) = minxi  {|| x-xi || : xi Ai}


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


V(Ai) = {p : ds(p, Ai) ≤ ds(p, Aj), ji,   i, j In}


Using above definitions, a set of the area Voronoi regions is V(A) = {V(A1), V(A2), . . . , V(An)}, 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.



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 A1, A2, . . . , An.