TY - JOUR

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

PY - 2018/8/1

Y1 - 2018/8/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 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).

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 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).

KW - Randomized algorithm

KW - Time-space trade-off

KW - Triangulation

KW - Voronoi diagram

UR - http://www.scopus.com/inward/record.url?scp=85045399673&partnerID=8YFLogxK

U2 - 10.1016/j.comgeo.2017.01.001

DO - 10.1016/j.comgeo.2017.01.001

M3 - Article

AN - SCOPUS:85045399673

SN - 0925-7721

VL - 73

SP - 35

EP - 45

JO - Computational Geometry

JF - Computational Geometry

ER -