NG-ALGORITHMS FOR MINIMUM LINK PATH AND RELATED PROBLEMS

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 be tween the points. The minimum link path problem is to compute a path c onsisting 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 poly gon problem asks for a minimum link closed path (girth) when R is an a nnular region defined by a pair of nested simple polygons. Efficient s equential algorithms based on greedy methods have been described for b oth problems. However, neither problem was known to be NC. In this pap er 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 invol ves new results on the parallel (NC1) computation of the complete visi bility polygon of a simple polygon from a set of points inside it, alo ng with an algebraic technique based on fractional linear transforms t hat 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 X processor product of these algorithm s is within a small polylog factor of the best known sequential algori thms for the respective problems. (C) 1995 Academic Press, Inc.