Finding the shortest path of a disc among polygonal obstacles using a radius-independent graph

摘要

An algorithm for finding the shortest path of a disc among a set of polygonal obstacles is presented. Let N/sub t/ denote the total number of obstacle vertices and N/sub c/ the number of convex vertices. Our algorithm uses a radius-independent data structure called extended tangent graph (ETG) which registers collision-free tangents of the obstacles according to different discs and takes O(N/sub c//sup 2/) space. The ETG depends only on original obstacles, and it is constructed in advance without using any information about the disc in O((N/sub c/+k)N/sub t/) computation time, where k is the number of outer common tangents of the obstacles. It takes O(N/sub t/logN/sub t/) time to partially update the ETG to reflect the start and goal of a given disc. The shortest path is planned by a graph-search algorithm.