Time-space trade-offs for triangulating a simple polygon

Boris Aronov; Matias Korman; Simon Pratt; André Van Renssen; Marcel Roeloffzen

doi:10.4230/LIPIcs.SWAT.2016.30

Time-space trade-offs for triangulating a simple polygon

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

3 Citations (Scopus)

105 Downloads (Pure)

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 ∈ O(n). The algorithm runs in O(n²/s + n(log s) log⁵ (n/s)) expected time using O(s) variables, for any s ∈ O(n). In particular, when s ∈ O(n/log n log⁵ log n) algorithm runs in O(n²/s) expected time.

Original language	English
Title of host publication	15th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2016
Editors	R. Pagh
Place of Publication	Dagstuhl
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Chapter	12
ISBN (Electronic)	9783959770118
DOIs	https://doi.org/10.4230/LIPIcs.SWAT.2016.30
Publication status	Published - 1 Jun 2016
Externally published	Yes
Event	15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) - Reykjavik, Iceland Duration: 22 Jun 2016 → 24 Jun 2016 Conference number: 15

Publication series

Name	Leibniz International Proceedings in Informatics (LIPIcs)
Volume	53
ISSN (Print)	1868-8969

Conference

Conference	15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Abbreviated title	SWAT 2016
Country/Territory	Iceland
City	Reykjavik
Period	22/06/16 → 24/06/16

Funding

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.

Keywords

Shortest path
Simple polygon
Time-space trade-off
Triangulation

Access to Document

10.4230/LIPIcs.SWAT.2016.30

publishers versionFinal published version, 556 KBLicence: CC BY

Cite this

Aronov, B., Korman, M., Pratt, S., Van Renssen, A., & Roeloffzen, M. (2016). Time-space trade-offs for triangulating a simple polygon. In R. Pagh (Ed.), 15th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2016 Article 30 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 53). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SWAT.2016.30

@inproceedings{e7428953654a44049833cf8eebd0a719,

title = "Time-space trade-offs for triangulating a simple polygon",

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 ∈ 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.",

keywords = "Shortest path, Simple polygon, Time-space trade-off, Triangulation",

author = "Boris Aronov and Matias Korman and Simon Pratt and {Van Renssen}, Andr{\'e} and Marcel Roeloffzen",

year = "2016",

month = jun,

day = "1",

doi = "10.4230/LIPIcs.SWAT.2016.30",

language = "English",

series = "Leibniz International Proceedings in Informatics (LIPIcs)",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

editor = "R. Pagh",

booktitle = "15th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2016",

note = "15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016), SWAT 2016 ; Conference date: 22-06-2016 Through 24-06-2016",

}

Aronov, B, Korman, M, Pratt, S, Van Renssen, A & Roeloffzen, M 2016, Time-space trade-offs for triangulating a simple polygon. in R Pagh (ed.), 15th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2016., 30, Leibniz International Proceedings in Informatics (LIPIcs), vol. 53, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016), Reykjavik, Iceland, 22/06/16. https://doi.org/10.4230/LIPIcs.SWAT.2016.30

Time-space trade-offs for triangulating a simple polygon. / Aronov, Boris; Korman, Matias; Pratt, Simon et al.
15th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2016. ed. / R. Pagh. Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. 30 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 53).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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 - Conference code: 15

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

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)

BT - 15th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2016

A2 - Pagh, R.

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

CY - Dagstuhl

T2 - 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)

Y2 - 22 June 2016 through 24 June 2016

ER -

Aronov B, Korman M, Pratt S, Van Renssen A, Roeloffzen M. Time-space trade-offs for triangulating a simple polygon. In Pagh R, editor, 15th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2016. Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2016. 30. (Leibniz International Proceedings in Informatics (LIPIcs)). doi: 10.4230/LIPIcs.SWAT.2016.30

Time-space trade-offs for triangulating a simple polygon

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this