ProV Logo
0
Time-Space Trade-offs for Triangulations...
Korman, Matias...

Free

Time-Space Trade-offs for Triangulations and Voronoi Diagrams by Korman, Matias ( Author )
Lemonjar Open Access
N.A
13-07-2015
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(nlogn) 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 Θ(logn) 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+nlognlogs) and a randomized s-workspace algorithm for finding the Voronoi diagram of S in expected time O((n2/s)logs+nlogslog∗s).
-
Article
pdf
36.88 KB
English
-
MYR 0.00
-
https://arxiv.org/abs/1507.03403
Share this eBook