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(n^2 / m) expected time, assuming m = O(n / log^2 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 linear-programming (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.
@InProceedings{harpeled:LIPIcs.SOCG.2015.111, author = {Har-Peled, Sariel}, title = {{Shortest Path in a Polygon using Sublinear Space}}, booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)}, pages = {111--125}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-83-5}, ISSN = {1868-8969}, year = {2015}, volume = {34}, editor = {Arge, Lars and Pach, J\'{a}nos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.111}, URN = {urn:nbn:de:0030-drops-50941}, doi = {10.4230/LIPIcs.SOCG.2015.111}, annote = {Keywords: Shortest path, violator spaces, limited space} }
Feedback for Dagstuhl Publishing