## Area of Voronoi Region

Consider a set of areas, A = {A_{1}, A_{2}, . . . , A_{n}}
in R^{2} where 1≤
n ≤ ∞.

### Assumptions

- Area A
_{i} is a connected closed set.
- Areas do not overlap each other, i.e.,

A_{i }
∩
A_{j} =
φ,
i ≠
j, i,j
I_{n
}.
- An Area A
_{i }is not necessarily Convex.
- 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_{1}),
V(A_{2}), . . . , 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

- Construct the live Voronoi diagram with L(A).
- Delete the Superfluous edges.
- 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_{1}, A_{2}, . . . , 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.