Time-space trade-offs for triangulations and Voronoi diagrams

Matias Korman; Wolfgang Mulzer; André Van Renssen; Marcel Roeloffzen; Paul Seiferth; Yannik Stein

doi:10.1007/978-3-319-21840-3_40

Time-space trade-offs for triangulations and Voronoi diagrams

Matias Korman
, Wolfgang Mulzer
, André Van Renssen
, Marcel Roeloffzen
, Paul Seiferth
, Yannik Stein

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

6 Citations (Scopus)

Abstract

Let S be a planar n-point set. A triangulation for S is a maximal plane straight-line graph with vertex set S. The Voronoi diagram for S is the subdivision of the plane into cells such that each cell has the same nearest neighbors in S. Classically, both structures can be computed in O(n log n) time and O(n) space. We study the situation when the available workspace is limited: given a parameter s ∈ {1,..., n}, an s-workspace algorithm has read-only access to an input array with the points from S in arbitrary order, and it may use only O(s) additional words of Θ(log n) bits for reading and writing intermediate data. The output should then be written to a write-only structure. We describe a deterministic s-workspace algorithm for computing a triangulation of S in time O(n²/s + n log n log s) and a randomized s-workspace algorithm for finding the Voronoi diagram of S in expected time O((n²/s) log s + n log s log^∗ s).

Original language	English
Title of host publication	Algorithms and Data Structures - 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings
Editors	F. Dehne, J.-R. Sack, U. Stege
Place of Publication	Berlin
Publisher	Springer
Pages	482-494
Number of pages	13
ISBN (Electronic)	9783319218403
ISBN (Print)	9783319218397
DOIs	https://doi.org/10.1007/978-3-319-21840-3_40
Publication status	Published - 1 Jan 2015
Externally published	Yes
Event	14th International Symposium on Algorithms and Data Structures (WADS 2015) - Victoria, Canada Duration: 5 Aug 2015 → 7 Aug 2015 Conference number: 14

Publication series

Name	Lecture Notes in Computer Science
Volume	9214
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	14th International Symposium on Algorithms and Data Structures (WADS 2015)
Abbreviated title	WADS 2015
Country/Territory	Canada
City	Victoria
Period	5/08/15 → 7/08/15

Funding

This work began while W. Mulzer, P. Seiferth, and Y. Stein visited the Tokuyama Laboratory at Tohoku University. We would like to thank Takeshi Tokuyama and all members of the lab for their hospitality and for creating a conducive and stimulating research environment. Appendix A

Access to Document

10.1007/978-3-319-21840-3_40

Cite this

Korman, M., Mulzer, W., Van Renssen, A., Roeloffzen, M., Seiferth, P., & Stein, Y. (2015). Time-space trade-offs for triangulations and Voronoi diagrams. In F. Dehne, J.-R. Sack, & U. Stege (Eds.), Algorithms and Data Structures - 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings (pp. 482-494). (Lecture Notes in Computer Science; Vol. 9214). Springer. https://doi.org/10.1007/978-3-319-21840-3_40

Korman, Matias ; Mulzer, Wolfgang ; Van Renssen, André et al. / Time-space trade-offs for triangulations and Voronoi diagrams. Algorithms and Data Structures - 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings. editor / F. Dehne ; J.-R. Sack ; U. Stege. Berlin : Springer, 2015. pp. 482-494 (Lecture Notes in Computer Science).

@inproceedings{3845fd9690034be8914a21e3dff8bc7b,

title = "Time-space trade-offs for triangulations and Voronoi diagrams",

abstract = "Let S be a planar n-point set. A triangulation for S is a maximal plane straight-line graph with vertex set S. The Voronoi diagram for S is the subdivision of the plane into cells such that each cell has the same nearest neighbors in S. Classically, both structures can be computed in O(n log n) time and O(n) space. We study the situation when the available workspace is limited: given a parameter s ∈ \{1,..., n\}, an s-workspace algorithm has read-only access to an input array with the points from S in arbitrary order, and it may use only O(s) additional words of Θ(log n) bits for reading and writing intermediate data. The output should then be written to a write-only structure. We describe a deterministic s-workspace algorithm for computing a triangulation of S in time O(n2/s + n log n log s) and a randomized s-workspace algorithm for finding the Voronoi diagram of S in expected time O((n2/s) log s + n log s log∗ s).",

author = "Matias Korman and Wolfgang Mulzer and \{Van Renssen\}, Andr{\'e} and Marcel Roeloffzen and Paul Seiferth and Yannik Stein",

year = "2015",

month = jan,

day = "1",

doi = "10.1007/978-3-319-21840-3\_40",

language = "English",

isbn = "9783319218397",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "482--494",

editor = "F. Dehne and J.-R. Sack and U. Stege",

booktitle = "Algorithms and Data Structures - 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings",

address = "Germany",

note = "14th International Symposium on Algorithms and Data Structures (WADS 2015), WADS 2015 ; Conference date: 05-08-2015 Through 07-08-2015",

}

Korman, M, Mulzer, W, Van Renssen, A, Roeloffzen, M, Seiferth, P & Stein, Y 2015, Time-space trade-offs for triangulations and Voronoi diagrams. in F Dehne, J-R Sack & U Stege (eds), Algorithms and Data Structures - 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings. Lecture Notes in Computer Science, vol. 9214, Springer, Berlin, pp. 482-494, 14th International Symposium on Algorithms and Data Structures (WADS 2015), Victoria, Canada, 5/08/15. https://doi.org/10.1007/978-3-319-21840-3_40

Time-space trade-offs for triangulations and Voronoi diagrams. / Korman, Matias; Mulzer, Wolfgang; Van Renssen, André et al.
Algorithms and Data Structures - 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings. ed. / F. Dehne; J.-R. Sack; U. Stege. Berlin: Springer, 2015. p. 482-494 (Lecture Notes in Computer Science; Vol. 9214).

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

TY - GEN

T1 - Time-space trade-offs for triangulations and Voronoi diagrams

AU - Korman, Matias

AU - Mulzer, Wolfgang

AU - Van Renssen, André

AU - Roeloffzen, Marcel

AU - Seiferth, Paul

AU - Stein, Yannik

N1 - Conference code: 14

PY - 2015/1/1

Y1 - 2015/1/1

N2 - Let S be a planar n-point set. A triangulation for S is a maximal plane straight-line graph with vertex set S. The Voronoi diagram for S is the subdivision of the plane into cells such that each cell has the same nearest neighbors in S. Classically, both structures can be computed in O(n log n) time and O(n) space. We study the situation when the available workspace is limited: given a parameter s ∈ {1,..., n}, an s-workspace algorithm has read-only access to an input array with the points from S in arbitrary order, and it may use only O(s) additional words of Θ(log n) bits for reading and writing intermediate data. The output should then be written to a write-only structure. We describe a deterministic s-workspace algorithm for computing a triangulation of S in time O(n2/s + n log n log s) and a randomized s-workspace algorithm for finding the Voronoi diagram of S in expected time O((n2/s) log s + n log s log∗ s).

AB - Let S be a planar n-point set. A triangulation for S is a maximal plane straight-line graph with vertex set S. The Voronoi diagram for S is the subdivision of the plane into cells such that each cell has the same nearest neighbors in S. Classically, both structures can be computed in O(n log n) time and O(n) space. We study the situation when the available workspace is limited: given a parameter s ∈ {1,..., n}, an s-workspace algorithm has read-only access to an input array with the points from S in arbitrary order, and it may use only O(s) additional words of Θ(log n) bits for reading and writing intermediate data. The output should then be written to a write-only structure. We describe a deterministic s-workspace algorithm for computing a triangulation of S in time O(n2/s + n log n log s) and a randomized s-workspace algorithm for finding the Voronoi diagram of S in expected time O((n2/s) log s + n log s log∗ s).

UR - https://www.scopus.com/pages/publications/84951771493

U2 - 10.1007/978-3-319-21840-3_40

DO - 10.1007/978-3-319-21840-3_40

M3 - Conference contribution

AN - SCOPUS:84951771493

SN - 9783319218397

T3 - Lecture Notes in Computer Science

SP - 482

EP - 494

BT - Algorithms and Data Structures - 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings

A2 - Dehne, F.

A2 - Sack, J.-R.

A2 - Stege, U.

PB - Springer

CY - Berlin

T2 - 14th International Symposium on Algorithms and Data Structures (WADS 2015)

Y2 - 5 August 2015 through 7 August 2015

ER -

Korman M, Mulzer W, Van Renssen A, Roeloffzen M, Seiferth P, Stein Y. Time-space trade-offs for triangulations and Voronoi diagrams. In Dehne F, Sack JR, Stege U, editors, Algorithms and Data Structures - 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings. Berlin: Springer. 2015. p. 482-494. (Lecture Notes in Computer Science). doi: 10.1007/978-3-319-21840-3_40

Time-space trade-offs for triangulations and Voronoi diagrams

Abstract

Publication series

Conference

Funding

Access to Document

Other files and links

Fingerprint

Cite this