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 proceedingConference contributionAcademicpeer-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(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).

Original languageEnglish
Title of host publicationAlgorithms and Data Structures - 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings
EditorsF. Dehne, J.-R. Sack, U. Stege
Place of PublicationBerlin
PublisherSpringer
Pages482-494
Number of pages13
ISBN (Electronic)9783319218403
ISBN (Print)9783319218397
DOIs
Publication statusPublished - 1 Jan 2015
Externally publishedYes
Event14th International Symposium on Algorithms and Data Structures (WADS 2015) - Victoria, Canada
Duration: 5 Aug 20157 Aug 2015
Conference number: 14

Publication series

NameLecture Notes in Computer Science
Volume9214
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference14th International Symposium on Algorithms and Data Structures (WADS 2015)
Abbreviated titleWADS 2015
CountryCanada
CityVictoria
Period5/08/157/08/15

Fingerprint

Dive into the research topics of 'Time-space trade-offs for triangulations and Voronoi diagrams'. Together they form a unique fingerprint.

Cite this