B. Prasad et al., A POLYNOMIAL-TIME ALGORITHM FOR AN EXACT ENCODING OF SPACE CONTAININGPOLYGONAL OBSTACLES, International journal of computer mathematics, 51(3-4), 1994, pp. 141-156
We address the problem of collision free navigation of a point robot a
mong polygonal obstacles in a bounded known terrain in two dimensional
space. The obstacles could be convex or concave polygons. We consider
a combinatorial approach to the problem and focus on partitioning the
terrain into distinct regions and encoding these regions. We then bui
ld a region-graph whose nodes represent the regions and every pair of
neighbouring regions (nodes) are connected by an edge. We propose an O
(n) preprocessing algorithm to do this. This converts the problem of n
avigation from a source point to a destination point into a problem of
finding a path in a planar graph from one of its nodes to another in
O(n2 log n) time. The shortest path is derivable in O(n4) time. The ex
tension of the algorithm for three-dimensional space is also discussed
.