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 -