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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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 Univ, UT 84322 USA.
2019 (English)In: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 81, no 1, p. 289-316Article in journal (Refereed) Published
Abstract [en]

We present a new algorithm for finding minimum-link rectilinear paths among rectilinear obstacles in the plane. Given a triangulated rectilinear domain of h pairwise-disjoint rectilinear obstacles with a total of n vertices, our algorithm can find a minimum-link rectilinear path between any two points in O(n+hlogh) time. Further, within the same time our algorithm can build an O(n)-size data structure for any source point s, such that given any query point t, the number of edges of a minimum-link rectilinear path from s to t can be computed in O(logn) time and the actual path can be output in additional time linear in the number of the edges of the path. The previously best algorithms for the problems run in O(nlogn) time.

Place, publisher, year, edition, pages
SPRINGER , 2019. Vol. 81, no 1, p. 289-316
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:liu:diva-154105DOI: 10.1007/s00453-018-0446-1ISI: 000455323200012OAI: oai:DiVA.org:liu-154105DiVA, id: diva2:1283557
Note

Funding Agencies|US-Israel Binational Science Foundation [2010074]; National Science Foundation [CCF-1018388, CCF-1526406]; NSF [CCF-1317143]

Available from: 2019-01-29 Created: 2019-01-29 Last updated: 2019-01-29

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Search in DiVA

By author/editor
Polishchuk, Valentin
By organisation
Communications and Transport SystemsFaculty of Science & Engineering
In the same journal
Algorithmica
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 86 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf