TY - GEN

T1 - Shortest Path in a Polygon using Sublinear Space

AU - Har-Peled, Sariel

PY - 2015/6/1

Y1 - 2015/6/1

N2 - We resolve an open problem due to Tetsuo Asano, showing how to compute the shortest path in a polygon, given in a read only memory, using sublinear space and subquadratic time. Specifically, given a simple polygon P with n vertices in a read only memory, and additional working memory of size m, the new algorithm computes the shortest path (in P) in O(n2/m) expected time, assuming m = O(n/ log2 n). This requires several new tools, which we believe to be of independent interest. Specifically, we show that violator space problems, an abstraction of low dimensional linearprogramming (and LP-type problems), can be solved using constant space and expected linear time, by modifying Seidel s linear programming algorithm and using pseudo-random sequences.

AB - We resolve an open problem due to Tetsuo Asano, showing how to compute the shortest path in a polygon, given in a read only memory, using sublinear space and subquadratic time. Specifically, given a simple polygon P with n vertices in a read only memory, and additional working memory of size m, the new algorithm computes the shortest path (in P) in O(n2/m) expected time, assuming m = O(n/ log2 n). This requires several new tools, which we believe to be of independent interest. Specifically, we show that violator space problems, an abstraction of low dimensional linearprogramming (and LP-type problems), can be solved using constant space and expected linear time, by modifying Seidel s linear programming algorithm and using pseudo-random sequences.

KW - Limited space

KW - Shortest path

KW - Violator spaces

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

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

U2 - 10.4230/LIPIcs.SOCG.2015.111

DO - 10.4230/LIPIcs.SOCG.2015.111

M3 - Conference contribution

AN - SCOPUS:84958185632

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 111

EP - 125

BT - 31st International Symposium on Computational Geometry, SoCG 2015

A2 - Pach, Janos

A2 - Pach, Janos

A2 - Arge, Lars

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 31st International Symposium on Computational Geometry, SoCG 2015

Y2 - 22 June 2015 through 25 June 2015

ER -