A POLYNOMIAL-TIME ALGORITHM FOR AN EXACT ENCODING OF SPACE CONTAININGPOLYGONAL OBSTACLES

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 .