Minimum-link paths among obstacles in the plane
Given a set of nonintersecting polygonal obstacles in the plane, the link distance between two points s and t is the minimum number of edges required to form a polygonal path connecting s to t that avoids all obstacles. We present an algorithm that computes the link distance (and a corresponding min...
|Published in:||Algorithmica : an international journal in computer science, Vol. 8, No. 1/6 (1992), p. 431-459|
|Other Involved Persons:||;|
|Item Description:||Joseph Mitchell was partially supported by NSF Grants IRI-8710858 and ECSE-8857642, and by a grant from Hughes Research Laboratories. This work was begun while Günter Rote and Gerhard Woeginger were at the Freie Universität Berlin, Fachbereich Mathematik, Institut für Informatik, and it was partially supported by the ESPRIT II Basic Research Actions Program of the EC under Contract No. 3075 (project ALCOM). Gerhard Woeginger acknowledges the support by the Fonds zur Förderung der Wissenschaftlichen Forschung, Projekt S32/01. Communicated by Mikhail J. Atallah.|
|QR Code:||Show QR Code|