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 [Mathematical Expression Omitted] 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] log [N.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.