Time-Space Trade-offs for Triangulating a Simple Polygon

Authors Boris Aronov, Matias Korman, Simon Pratt, André van Renssen, Marcel Roeloffzen



PDF
Thumbnail PDF

File

LIPIcs.SWAT.2016.30.pdf
  • Filesize: 0.54 MB
  • 12 pages

Document Identifiers

Author Details

Boris Aronov
Matias Korman
Simon Pratt
André van Renssen
Marcel Roeloffzen

Cite AsGet BibTex

Boris Aronov, Matias Korman, Simon Pratt, André van Renssen, and Marcel Roeloffzen. Time-Space Trade-offs for Triangulating a Simple Polygon. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 30:1-30:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.SWAT.2016.30

Abstract

An s-workspace algorithm is an algorithm that has read-only access to the values of the input, write-only access to the output, and only uses O(s) additional words of space. We give a randomized s-workspace algorithm for triangulating a simple polygon P of n vertices, for any s up to n. The algorithm runs in O(n^2/s+n(log s)log^5(n/s)) expected time using O(s) variables, for any s up to n. In particular, the algorithm runs in O(n^2/s) expected time for most values of s.
Keywords
  • simple polygon
  • triangulation
  • shortest path
  • time-space trade-off

Metrics

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

References

  1. B. Aronov, M. Korman, S. Pratt, A. van Renssen, and M. Roeloffzen. Time-space trade-offs for triangulating a simple polygon. CoRR, abs/1509.07669, 2015. URL: http://arxiv.org/abs/1509.07669.
  2. T. Asano, K. Buchin, M. Buchin, M. Korman, W. Mulzer, G. Rote, and A. Schulz. Memory-constrained algorithms for simple polygons. Computational Geometry: Theory and Applications, 46(8):959-969, 2013. Google Scholar
  3. T. Asano and D. Kirkpatrick. Time-space tradeoffs for all-nearest-larger-neighbors problems. In Proc. 13th Int. Conf. Algorithms and Data Structures (WADS), pages 61-72, 2013. Google Scholar
  4. T. Asano, W. Mulzer, G. Rote, and Y. Wang. Constant-work-space algorithms for geometric problems. Journal of Computational Geometry, 2(1):46-68, 2011. Google Scholar
  5. L. Barba, M. Korman, S. Langerman, K. Sadakane, and R. I. Silveira. Space-time trade-offs for stack-based algorithms. Algorithmica, 72(4):1097-1129, 2015. URL: http://dx.doi.org/10.1007/s00453-014-9893-5.
  6. L. Barba, M. Korman, S. Langerman, and R. I. Silveira. Computing the visibility polygon using few variables. Computational Geometry: Theory and Applications, 47(9):918-926, 2013. Google Scholar
  7. B. Chazelle. Triangulating a simple polygon in linear time. Discrete & Computational Geometry, 6:485-524, 1991. URL: http://dx.doi.org/10.1007/BF02574703.
  8. S. Har-Peled. Shortest path in a polygon using sublinear space. In Proceedings of the 31st International Symposium on Compututational Geometry (SoCG), pages 111-125, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.SOCG.2015.111.
  9. M. Korman. Memory-constrained algorithms. In Ming-Yang Kao, editor, Encyclopedia of Algorithms, pages 1-7. Springer Berlin Heidelberg, 2015. URL: http://dx.doi.org/10.1007/978-3-642-27848-8_586-1.
  10. M. Korman, W. Mulzer, M. Roeloffzen, A. v. Renssen, P. Seiferth, and Y. Stein. Time-space trade-offs for triangulations and voronoi diagrams. In Proc. 14th Int. Conf. Algorithms and Data Structures (WADS), pages 482-494, 2015. Google Scholar
  11. J. E. Savage. Models of Computation: Exploring the Power of Computing. Addison-Wesley, 1998. 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