Time-space trade-offs for triangulations and Voronoi diagrams

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

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)
169 Downloads (Pure)

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 all points in a cell have the same nearest neighbor in S. Classically, both structures can be computed in O(nlog 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 an arbitrary triangulation of S in time O(n2/s+nlog nlog s) and a randomized s-workspace algorithm for finding the Voronoi diagram of S in expected time O((n2/s)log s+nlog slog* s).

Original languageEnglish
Pages (from-to)35-45
Number of pages11
JournalComputational Geometry
Volume73
DOIs
Publication statusPublished - 1 Aug 2018
Externally publishedYes

Keywords

  • Randomized algorithm
  • Time-space trade-off
  • Triangulation
  • Voronoi diagram

Fingerprint

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

Cite this