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

Keywords

  • Limited space
  • Shortest path
  • Violator spaces

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Shortest Path in a Polygon using Sublinear Space'. Together they form a unique fingerprint.

Cite this