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

### Assumptions

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.

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

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

### Reload 