Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2016.30
URN: urn:nbn:de:0030-drops-60522
URL: https://drops.dagstuhl.de/opus/volltexte/2016/6052/
Aronov, Boris ; Korman, Matias ; Pratt, Simon ; van Renssen, André ; Roeloffzen, Marcel
Time-Space Trade-offs for Triangulating a Simple Polygon
| pdf-format: |
|
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.
BibTeX - Entry
@InProceedings{aronov_et_al:LIPIcs:2016:6052,
author = {Boris Aronov and Matias Korman and Simon Pratt and André van Renssen and Marcel Roeloffzen},
title = {{Time-Space Trade-offs for Triangulating a Simple Polygon}},
booktitle = {15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
pages = {30:1--30:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-011-8},
ISSN = {1868-8969},
year = {2016},
volume = {53},
editor = {Rasmus Pagh},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6052},
URN = {urn:nbn:de:0030-drops-60522},
doi = {10.4230/LIPIcs.SWAT.2016.30},
annote = {Keywords: simple polygon, triangulation, shortest path, time-space trade-off}
}
| Keywords: | simple polygon, triangulation, shortest path, time-space trade-off | |
| Seminar: | 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) | |
| Issue date: | 2016 | |
| Date of publication: | 22.06.2016 |
