Shortest Path in a Polygon using Sublinear Space

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication31st International Symposium on Computational Geometry, SoCG 2015
EditorsJanos Pach, Janos Pach, Lars Arge
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages111-125
Number of pages15
ISBN (Electronic)9783939897835
DOIs
StatePublished - Jun 1 2015
Event31st International Symposium on Computational Geometry, SoCG 2015 - Eindhoven, Netherlands
Duration: Jun 22 2015Jun 25 2015

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume34
ISSN (Print)1868-8969

Other

Other31st International Symposium on Computational Geometry, SoCG 2015
CountryNetherlands
CityEindhoven
Period6/22/156/25/15

    Fingerprint

Keywords

  • Limited space
  • Shortest path
  • Violator spaces

ASJC Scopus subject areas

  • Software

Cite this

Har-Peled, S. (2015). Shortest Path in a Polygon using Sublinear Space. In J. Pach, J. Pach, & L. Arge (Eds.), 31st International Symposium on Computational Geometry, SoCG 2015 (pp. 111-125). (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 34). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SOCG.2015.111