Minimum-link paths revisited
2014 (English)In: Computational Geometry, ISSN 0925-7721, Vol. 47, no 6, 651-667 p.Article in journal (Refereed) PublishedText
A path or a polygonal domain is C-oriented if the orientations of its edges belong to a set of C given orientations; this is a generalization of the notable rectilinear case (C=2C=2). We study exact and approximation algorithms for minimum-link C-oriented paths and paths with unrestricted orientations, both in C-oriented and in general domains.
Our two main algorithms are as follows:
A subquadratic-time algorithm with a non-trivial approximation guarantee for general (unrestricted-orientation) minimum-link paths in general domains.
An algorithm to find a minimum-link C-oriented path in a C-oriented domain. Our algorithm is simpler and more time-space efficient than the prior algorithm.
We also obtain several related results:•3SUM-hardness of determining the link distance with unrestricted orientations (even in a rectilinear domain).
•An optimal algorithm for finding a minimum-link rectilinear path in a rectilinear domain. The algorithm and its analysis are simpler than the existing ones.
•An extension of our methods to find a C-oriented minimum-link path in a general (not necessarily C-oriented) domain.
•A more efficient algorithm to compute a 2-approximate C-oriented minimum-link path.
•A notion of “robust” paths. We show how minimum-link C-oriented paths approximate the robust paths with unrestricted orientations to within an additive error of 1.
Place, publisher, year, edition, pages
2014. Vol. 47, no 6, 651-667 p.
Path planning;Link distance;Approximations;3SUM-hardness
IdentifiersURN: urn:nbn:se:liu:diva-128015DOI: 10.1016/j.comgeo.2013.12.005OAI: oai:DiVA.org:liu-128015DiVA: diva2:928745