Document Open Access Logo

Shortest Path in a Polygon using Sublinear Space

Author Sariel Har-Peled

PDF
Thumbnail PDF

File

LIPIcs.SOCG.2015.111.pdf
  • Filesize: 0.68 MB
  • 15 pages

Document Identifiers

Author Details

Sariel Har-Peled

Cite As Get BibTex

Sariel Har-Peled. Shortest Path in a Polygon using Sublinear Space. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 111-125, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.SOCG.2015.111

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(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.

Subject Classification

Keywords
  • Shortest path
  • violator spaces
  • limited space

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. T. Asano, K. Buchin, M. Buchin, M. Korman, W. Mulzer, G. Rote, and A. Schulz. Memory-constrained algorithms for simple polygons. Comput. Geom. Theory Appl., 46(8):959-969, 2013. Google Scholar
  2. T. Asano, K. Buchin, M. Buchin, M. Korman, W. Mulzer, G. Rote, and A. Schulz. Reprint of: Memory-constrained algorithms for simple polygons. Comput. Geom. Theory Appl., 47(3):469-479, 2014. Google Scholar
  3. M. de Berg, O. Cheong, M. van Kreveld, and M. H. Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag, Santa Clara, CA, USA, 3rd edition, 2008. Google Scholar
  4. Y. Brise and B. Gärtner. Clarkson’s algorithm for violator spaces. Comput. Geom. Theory Appl., 44(2):70-81, 2011. Google Scholar
  5. B. Chazelle, D. Liu, and A. Magen. Sublinear geometric algorithms. SIAM J. Comput., 35(3):627-646, 2005. Google Scholar
  6. B. Chazelle and J. Matoušek. On linear-time deterministic algorithms for optimization problems in fixed dimension. J. Algorithms, 21:579-597, 1996. Google Scholar
  7. K. L. Clarkson. Las Vegas algorithms for linear and integer programming. J. Assoc. Comput. Mach., 42:488-499, 1995. Google Scholar
  8. K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II. Discrete Comput. Geom., 4:387-421, 1989. Google Scholar
  9. S. J. Fortune. A sweepline algorithm for Voronoi diagrams. Algorithmica, 2:153-174, 1987. Google Scholar
  10. B. Gärtner, J. Matoušek, L. Rüst, and P. Šavroň. Violator spaces: Structure and algorithms. In Proc. 14th Annu. European Sympos. Algorithms\CNFESA, pages 387-398, 2006. Google Scholar
  11. B. Gärtner, J. Matoušek, L. Rüst, and P. Šavroň. Violator spaces: Structure and algorithms. Discrete Appl. Math., 156(11):2124-2141, 2008. Google Scholar
  12. L. J. Guibas and J. Hershberger. Optimal shortest path queries in a simple polygon. J. Comput. Syst. Sci., 39(2):126-152, October 1989. Google Scholar
  13. S. Har-Peled. Geometric Approximation Algorithms, volume 173 of Mathematical Surveys and Monographs. Amer. Math. Soc., Boston, MA, USA, 2011. Google Scholar
  14. S. Har-Peled. Quasi-polynomial time approximation scheme for sparse subsets of polygons. In Proc. 30th Annu. Sympos. Comput. Geom.\CNFSoCG, pages 120-129, 2014. Google Scholar
  15. S. Har-Peled. Shortest path in a polygon using sublinear space. CoRR, abs/1412.0779, 2014. Google Scholar
  16. P. Indyk. Stable distributions, pseudorandom generators, embeddings, and data stream computation. J. Assoc. Comput. Mach., 53(3):307-323, 2006. Google Scholar
  17. D. T. Lee and F. P. Preparata. Euclidean shortest paths in the presence of rectilinear barriers. Networks, 14:393-410, 1984. Google Scholar
  18. N. Megiddo. Linear programming in linear time when the dimension is fixed. J. Assoc. Comput. Mach., 31:114-127, 1984. Google Scholar
  19. K. Mulmuley. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs, NJ, 1994. Google Scholar
  20. L. Y. Rüst. The P-Matrix Linear Complementarity Problem - Generalizations and Specializations. PhD thesis, ETH, 2007. Diss. ETH No. 17387. Google Scholar
  21. P. Šavroň. Abstract models of optimization problems. PhD thesis, Charles University, 2007. URL: http://kam.mff.cuni.cz/~xofon/thesis/diplomka.pdf.
  22. R. Seidel. Small-dimensional linear programming and convex hulls made easy. Discrete Comput. Geom., 6:423-434, 1991. Google Scholar
  23. M. Sharir and E. Welzl. A combinatorial bound for linear programming and related problems. In Proc. 9th Sympos. Theoret. Aspects Comput. Sci., volume 577 of Lect. Notes in Comp. Sci., pages 569-579, London, UK, 1992. Springer-Verlag. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact