N C-algorithms for minimum link path and related problems

Chandru, V. ; Ghosh, S. K. ; Maheshwari, A. ; Rajan, V. T. ; Saluja, S. J. (1995) N C-algorithms for minimum link path and related problems Journal of Algorithms, 19 (2). pp. 173-203. ISSN 0196-6774

Full text not available from this repository.

Official URL: http://linkinghub.elsevier.com/retrieve/pii/S01966...

Related URL: http://dx.doi.org/10.1006/jagm.1995.1033


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 N C. 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 (N C) 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 x processor product of these algorithms is within a small polylog factor of the best known sequential algorithms for the respective problems.

Item Type:Article
Source:Copyright of this article belongs to Elsevier Science.
ID Code:5536
Deposited On:19 Oct 2010 11:59
Last Modified:02 Jun 2011 08:35

Repository Staff Only: item control page