liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Minimum-link paths revisited
Stony Brook University, USA.
Linköping University, Department of Science and Technology, Communications and Transport Systems. Linköping University, The Institute of Technology. University of Helsinki, Finland.
University of Helsinki, Finland .
2014 (English)In: Computational geometry, ISSN 0925-7721, E-ISSN 1879-081X, Vol. 47, no 6, 651-667 p.Article in journal (Refereed) Published
Abstract [en]

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 = 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
Elsevier, 2014. Vol. 47, no 6, 651-667 p.
Keyword [en]
Path planning; Link distance; Approximations; 3SUM-hardness
National Category
Engineering and Technology
URN: urn:nbn:se:liu:diva-106274DOI: 10.1016/j.comgeo.2013.12.005ISI: 000333728300003OAI: diva2:715765
Available from: 2014-05-06 Created: 2014-05-05 Last updated: 2014-05-14Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Polishchuk, Valentin
By organisation
Communications and Transport SystemsThe Institute of Technology
In the same journal
Computational geometry
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 21 hits
ReferencesLink to record
Permanent link

Direct link