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_t denote the total number of obstacle vertices and N_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_c²) space. The ETG depends only on original obstacles, and it is constructed in advance without using any information about the disc in O((N_c+k)N_t) computation time, where k is the number of outer common tangents of the obstacles. It takes O(N_tlogN_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