NC-algorithms for minimum link path and related problems

Abstract

The link metric, defined on a constrained region R of the plane, sets the distance between a pair of points in R to equal the minimum number of line segments or links that are needed to construct a path in R between the points. The minimum link path problem is to compute a path consisting of the minimum number of links between two points in R, when R is the inside of an n-sided simple polygon. The minimum nested polygon problem asks for a minimum link closed path (girth) when R is an annular region defined by a pair of nested simple polygons. Efficient sequential algorithms based on greedy methods have been described for both problems. However, neither problem was known to be NC. In this paper we present algorithms that require O(log n loglog n) time and O(n) space using O(n) processors for both problems. The approach used involves new results on the parallel (NC1) computation of the complete visibility polygon of a simple polygon from a set of points inside it, along with an algebraic technique based on fractional linear transforms that permits effective parallelization of the "greedy" computations. The complexity results of this paper are with respect to the CREW-PRAM model of computation. The time × processor product of these algorithms is within a small polylog factor of the best known sequential algorithms for the respective problems. © 1995 Academic Press, Inc.