Document Open Access Logo

A New Balanced Subdivision of a Simple Polygon for Time-Space Trade-off Algorithms

Authors Eunjin Oh, Hee-Kap Ahn

PDF

File

Thumbnail PDF
PDF
LIPIcs.ISAAC.2017.61.pdf
  • Filesize: 0.61 MB
  • 12 pages

Document Identifiers

Subject Classification

Keywords
  • Time-space trade-off
  • simple polygon
  • shortest path
  • shortest path tree

Metrics

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

Abstract

We are given a read-only memory for input and a write-only stream for output. For a positive integer parameter s, an s-workspace algorithm is an algorithm using only O(s) words of workspace in addition to the memory for input. In this paper, we present an O(n^2/s)-time s-workspace algorithm for subdividing a simple polygon into O(\min\{n/s,s\}) subpolygons of complexity O(\max\{n/s,s\}).

As applications of the subdivision, the previously best known time-space trade-offs for the following three geometric problems are improved immediately: (1) computing the shortest path between two points inside a simple n-gon, (2) computing the shortest path tree from a point inside a simple n-gon, (3) computing a triangulation of a simple n-gon. In addition, we improve the algorithm for the second problem even further.

Cite As Get BibTex

Eunjin Oh and Hee-Kap Ahn. A New Balanced Subdivision of a Simple Polygon for Time-Space Trade-off Algorithms. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 61:1-61:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ISAAC.2017.61

Author Details

Eunjin Oh
Hee-Kap Ahn

References

  1. Boris Aronov, Matias Korman, Simon Pratt, André van Renssen, and Marcel Roeloffzen. Time-space trade-offs for triangulating a simple polygon. Journal of Computational Geometry, 8(1):105-124, 2017. Google Scholar
  2. Tetsuo Asano, Kevin Buchin, Maike Buchin, Matias Korman, Wolfgang Mulzer, Günter Rote, and André Schulz. Memory-constrained algorithms for simple polygons. Computational Geometry, 46(8):959-969, 2013. Google Scholar
  3. Tetsuo Asano and David Kirkpatrick. Time-space tradeoffs for all-nearest-larger-neighbors problems. In Proceedings of the 13th Algorithms and Data Strucutres Symposium (WADS 2013), pages 61-72, 2013. Google Scholar
  4. Luis Barba, Matias Korman, Stefan Langerman, Kunihiko Sadakane, and Rodrigo I. Silveira. Space-time trade-offs for stack-based algorithms. Algorithmica, 72(4):1097-1129, 2015. Google Scholar
  5. Bernard Chazelle. Triangulating a simple polygon in linear time. Discrete &Computational Geometry, 6(3):485-524, 1991. Google Scholar
  6. Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag TELOS, 2008. Google Scholar
  7. Greg N. Frederickson. Upper bounds for time-space trade-offs in sorting and selection. Journal of Computer and System, 34(1):19-26, 1987. Google Scholar
  8. Leonidas Guibas, John Hershberger, Daniel Leven, Micha Sharir, and Robert E. Tarjan. Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica, 2(1):209-233, 1987. Google Scholar
  9. Sariel Har-Peled. Shortest path in a polygon using sublinear space. Journal of Computational Geometry, 7(2):19-45, 2015. Google Scholar
  10. Eunjin Oh and Hee-Kap Ahn. A new balanced subdivision of a simple polygon for time-space trade-off algorithms, 2017. URL: http://arxiv.org/abs/1709.09932.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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