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...

Full description

Bibliographic Details
Published in:Algorithmica : an international journal in computer science, Vol. 8, No. 1/6 (1992), p. 431-459
Main Author: Mitchell, B.
Other Involved Persons: Rote, Günter ; Woeginger, Gerhard
Format: electronic Article
Language:English
ISSN:1432-0541
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.
Physical Description:Online-Ressource
DOI:10.1007/BF01758855
Subjects:
QR Code: Show QR Code