Reif and Sun derive an upper bound on the sum of boundary lengths of obstacles in a two-dimensional region C under three assumptions:
- The free space F (subregion of C free of obstacles) is &egr;-visible, that is, from any point in F, a viewer can see at least &egr; of the area of F.
- F is contained by a rectangle whose aspect ratio is a constant.
- The ratio of areas of C and F is a constant.
Let &mgr; (X) denote the area of a region X. The bound is O(√n&mgr;(F) / &egr;). However, it must be interpreted according to the geometric nature of the obstacles.
If the obstacles are convex with piecewise smooth (differentiable to all orders) boundaries, then n is the number of obstacles. If the obstacles are polygons, then n is their total number of edges. In the polygonal case, the authors show that the bound is tight by construction. There is a partial extension of this result to three dimensions.
The paper contains a review of applications of the visibility concept, especially to road map planning, which is a key approach to robotics, and variations of the art gallery problem in which guard points are chosen to ensure that all regions of the gallery are under surveillance. Road map problems are, in some cases, provably intractable and most of the art gallery problems are nondeterministic polynomial time (NP) hard. Without citing all of the hardness results, one intriguing result, due to Eidenbenz et al., is that a certain art gallery problem cannot be polynomial time approximated to within (1 - &egr;)/(12 ln n) of the minimum number of guards unless NP is contained in TIME(nO(log log n)). The paper concludes with some conjectures on the application of the paper’s upper bound result to probabilistic road map planning.
