LIPIcs.ISAAC.2017.61.pdf
- Filesize: 0.61 MB
- 12 pages
Document
A New Balanced Subdivision of a Simple Polygon for Time-Space Trade-off Algorithms
Authors
-
Part of:
Volume:
28th International Symposium on Algorithms and Computation (ISAAC 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Algorithms and Computation (ISAAC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-12-07
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
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.
Subject Classification
Keywords
- Time-space trade-off
- simple polygon
- shortest path
- shortest path tree
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
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.
-
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.
-
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.
-
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.
-
Bernard Chazelle. Triangulating a simple polygon in linear time. Discrete &Computational Geometry, 6(3):485-524, 1991.
-
Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag TELOS, 2008.
-
Greg N. Frederickson. Upper bounds for time-space trade-offs in sorting and selection. Journal of Computer and System, 34(1):19-26, 1987.
-
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.
-
Sariel Har-Peled. Shortest path in a polygon using sublinear space. Journal of Computational Geometry, 7(2):19-45, 2015.
- 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.