TY - GEN
T1 - Time-space trade-offs for triangulating a simple polygon
AU - Aronov, Boris
AU - Korman, Matias
AU - Pratt, Simon
AU - Van Renssen, André
AU - Roeloffzen, Marcel
N1 - Funding Information:
Work on this paper by B. A. was supported in part by NSF Grants CCF-11-17336 and CCF-12-18791. M. K. was supported in part by the ELC project (MEXT KAKENHI No. 12H00855 and 15H02665). S. P. was supported in part by the Ontario Graduate Scholarship and The Natural Sciences and Engineering Research Council of Canada. The authors would like to thank Jean-François Baffier, Man-Kwun Chiu, Wolfgang Mulzer and Takeshi Tokuyama for valuable discussion in the creation of this paper.
Publisher Copyright:
© Boris Aronov, Matias Korman, André van Renssen, Marcel Roeloffzen, and Simon Pratt.
PY - 2016/6/1
Y1 - 2016/6/1
N2 - 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 ∈ O(n). The algorithm runs in O(n2/s + n(log s) log5 (n/s)) expected time using O(s) variables, for any s ∈ O(n). In particular, when s ∈ O(n/log n log5 log n) algorithm runs in O(n2/s) expected time.
AB - 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 ∈ O(n). The algorithm runs in O(n2/s + n(log s) log5 (n/s)) expected time using O(s) variables, for any s ∈ O(n). In particular, when s ∈ O(n/log n log5 log n) algorithm runs in O(n2/s) expected time.
KW - Shortest path
KW - Simple polygon
KW - Time-space trade-off
KW - Triangulation
UR - http://www.scopus.com/inward/record.url?scp=85011994891&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85011994891&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.SWAT.2016.30
DO - 10.4230/LIPIcs.SWAT.2016.30
M3 - Conference contribution
AN - SCOPUS:85011994891
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 30.1-30.12
BT - 15th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2016
A2 - Pagh, Rasmus
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 15th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2016
Y2 - 22 June 2016 through 24 June 2016
ER -