TY - GEN
T1 - An optimal algorithm for minimum-link rectilinear paths in triangulated rectilinear domains
AU - Mitchell, Joseph S.B.
AU - Polishchuk, Valentin
AU - Sysikaski, Mikko
AU - Wang, Haitao
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2015.
PY - 2015
Y1 - 2015
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/84950136497
U2 - 10.1007/978-3-662-47672-7_77
DO - 10.1007/978-3-662-47672-7_77
M3 - Conference contribution
AN - SCOPUS:84950136497
SN - 9783662476710
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 947
EP - 959
BT - Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings
A2 - Halldorsson, Magnus M.
A2 - Kobayashi, Naoki
A2 - Speckmann, Bettina
A2 - Iwama, Kazuo
PB - Springer Verlag
T2 - 42nd International Colloquium on Automata, Languages and Programming, ICALP 2015
Y2 - 6 July 2015 through 10 July 2015
ER -