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)

51 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

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

Keywords

Access to Document

Other files and links

Fingerprint

Cite this