A FRAMED-QUADTREE APPROACH FOR DETERMINING EUCLIDEAN SHORTEST PATHS IN A 2-D ENVIRONMENT

In this paper we investigate the problem of finding a Euclidean (L-2) shortest path between two distinct locations in a planar environment. We propose a novel cell decomposition approach which calculates an L-2 distance transform through the use of a circular path-planning wave. The proposed method is based an a mew data structure, called the frame d-quadtree, which combines together the accuracy of high resolution gr id-based path planning techniques with the efficiency of quadtree-base d techniques, hence having the advantages of both. The heart of this m ethod is a linear time algorithm for computing certain special dynamic Voronoi diagrams, The proposed method does not place any unrealistic constraints on obstacles or on the environment and represents an impro vement in accuracy and efficiency over traditional path planning appro aches in this area.