TY - GEN

T1 - Shortest non-crossing walks in the plane

AU - Erickson, Jeff

AU - Nayyeri, Amir

N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2011

Y1 - 2011

N2 - Let G be an n-vertex plane graph with non-negative edge weights, and let k terminal pairs be specified on h face boundaries. We present an algorithm to find k non-crossing walks in G of minimum total length that connect all terminal pairs, if any such walks exist, in 2o(h2)n log k time. The computed walks may overlap but may not cross each other or themselves. Our algorithm generalizes a result of Takahashi, Suzuki, and Nishizeki [Algorithmica 1996] for the special case h ≤ 2. We also describe an algorithm for the corresponding geometric problem, where the terminal points lie on the boundary of h polygonal obstacles of total complexity n, again in 2o(h2)n time, generalizing an algorithm of Papadopoulou [Int. J. Comput. Geom. Appl 1999] for the special case h ≤ 2. In both settings, shortest non-crossing walks can have complexity exponential in h. We also describe algorithms to determine in O(n) time whether the terminal pairs can be connected by any non-crossing walks.

AB - Let G be an n-vertex plane graph with non-negative edge weights, and let k terminal pairs be specified on h face boundaries. We present an algorithm to find k non-crossing walks in G of minimum total length that connect all terminal pairs, if any such walks exist, in 2o(h2)n log k time. The computed walks may overlap but may not cross each other or themselves. Our algorithm generalizes a result of Takahashi, Suzuki, and Nishizeki [Algorithmica 1996] for the special case h ≤ 2. We also describe an algorithm for the corresponding geometric problem, where the terminal points lie on the boundary of h polygonal obstacles of total complexity n, again in 2o(h2)n time, generalizing an algorithm of Papadopoulou [Int. J. Comput. Geom. Appl 1999] for the special case h ≤ 2. In both settings, shortest non-crossing walks can have complexity exponential in h. We also describe algorithms to determine in O(n) time whether the terminal pairs can be connected by any non-crossing walks.

UR - http://www.scopus.com/inward/record.url?scp=79955730102&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79955730102&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973082.25

DO - 10.1137/1.9781611973082.25

M3 - Conference contribution

AN - SCOPUS:79955730102

SN - 9780898719932

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 297

EP - 308

BT - Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011

PB - Association for Computing Machinery

ER -