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

Direct link
An Optimal Algorithm for Minimum-Link Rectilinear Paths in Triangulated Rectilinear Domains
SUNY Stony Brook, NY 11794 USA.
Linköping University, Department of Science and Technology, Communications and Transport Systems. Linköping University, Faculty of Science & Engineering.
Google, Switzerland.
Utah State University, UT 84322 USA.
2015 (English)In: Automata, Languages, and Programming, Pt I, SPRINGER-VERLAG BERLIN , 2015, Vol. 9134, 947-959 p.Conference paper (Refereed)
Abstract [en]

We present a new algorithm for finding minimum-link rectilinear paths among h rectilinear obstacles with a total of n vertices in the plane. After the plane is triangulated, for any point s, our algorithm builds an O(n)-size data structure in O(n+h log h) time, such that given any query point t, we can compute a minimum-link rectilinear path from s to t in O(log n + k) time, where k is the number of edges of the path, and the query time is O(log n) if we only want to know the value k. The previously best algorithm solves the problem in O(n log n) time.

Place, publisher, year, edition, pages
SPRINGER-VERLAG BERLIN , 2015. Vol. 9134, 947-959 p.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 (print), 1611-3349 (online) ; 9134
National Category
Civil Engineering
Identifiers
URN: urn:nbn:se:liu:diva-123168DOI: 10.1007/978-3-662-47672-7_77ISI: 000364317700077ISBN: 978-3-662-47672-7; 978-3-662-47671-0OAI: oai:DiVA.org:liu-123168DiVA: diva2:877269
Conference
42nd International Colloquium on Automata, Languages and Programming (ICALP)
Available from: 2015-12-06 Created: 2015-12-04 Last updated: 2015-12-06

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 SystemsFaculty of Science & Engineering
Civil Engineering

Search outside of DiVA

GoogleGoogle ScholarTotal: 1 downloads
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: 29 hits
ReferencesLink to record
Permanent link

Direct link