TY - GEN

T1 - Improved time-space trade-offs for computin Voronoi diagrams

AU - Banyassady, Bahareh

AU - Korman, Matias

AU - Mulzer, Wolfgang

AU - Van Renssen, André

AU - Roeloffzen, Marcel

AU - Seiferth, Paul

AU - Stein, Yannik

N1 - Publisher Copyright:
© Bahareh Banyassady, Matias Korman, Wolfgang Mulzer, André van Renssen, Marcel Roeloffzen, Paul Seiferth, and Yannik Stein.

PY - 2017/3/1

Y1 - 2017/3/1

N2 - Let P be a planar n-point set in general position. For k ∈ {1,⋯, n - 1}, the Voronoi diagram of order k is obtained by subdividing the plane into regions such that points in the same cell have the same set of nearest k neighbors in P. The (nearest point) Voronoi diagram (NVD) and the farthest point Voronoi diagram (FVD) are the particular cases of k = 1 and k = n - 1, respectively. It is known that the family of all higher-order Voronoi diagrams of order 1 to K for P can be computed in total time O(nK2 + n log n) using O(K2(n - K)) space. Also NVD and FVD can be computed in O (n log n) time using O(n) space. For s ∈ {1,⋯, n}, an s-workspace algorithm has random access to a read-only array with the sites of P in arbitrary order. Additionally, the algorithm may use O(s) words of Θ(logn) bits each for reading and writing intermediate data. The output can be written only once and cannot be accessed afterwards. We describe a deterministic s-workspace algorithm for computing an NVD and also an FVD for P that runs in O((n2/s) logs) time. Moreover, we generalize our s-workspace algorithm for computing the family of all higher-order Voronoi diagrams of P up to order K ∈ O(√s) in total time O(n2K6/s log1+ϵ K · (logs/logK)O(1)), for any fixed ϵ > 0. Previously, for Voronoi diagrams, the only known s-workspace algorithm was to find an NVD for P in expected time O((n2/s) log s + n log s log∗ s). Unlike the previous algorithm, our new method is very simple and does not rely on advanced data structures or random sampling techniques.

AB - Let P be a planar n-point set in general position. For k ∈ {1,⋯, n - 1}, the Voronoi diagram of order k is obtained by subdividing the plane into regions such that points in the same cell have the same set of nearest k neighbors in P. The (nearest point) Voronoi diagram (NVD) and the farthest point Voronoi diagram (FVD) are the particular cases of k = 1 and k = n - 1, respectively. It is known that the family of all higher-order Voronoi diagrams of order 1 to K for P can be computed in total time O(nK2 + n log n) using O(K2(n - K)) space. Also NVD and FVD can be computed in O (n log n) time using O(n) space. For s ∈ {1,⋯, n}, an s-workspace algorithm has random access to a read-only array with the sites of P in arbitrary order. Additionally, the algorithm may use O(s) words of Θ(logn) bits each for reading and writing intermediate data. The output can be written only once and cannot be accessed afterwards. We describe a deterministic s-workspace algorithm for computing an NVD and also an FVD for P that runs in O((n2/s) logs) time. Moreover, we generalize our s-workspace algorithm for computing the family of all higher-order Voronoi diagrams of P up to order K ∈ O(√s) in total time O(n2K6/s log1+ϵ K · (logs/logK)O(1)), for any fixed ϵ > 0. Previously, for Voronoi diagrams, the only known s-workspace algorithm was to find an NVD for P in expected time O((n2/s) log s + n log s log∗ s). Unlike the previous algorithm, our new method is very simple and does not rely on advanced data structures or random sampling techniques.

KW - Memory-constrained model

KW - Time-space trade-off

KW - Voronoi diagram

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

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

U2 - 10.4230/LIPIcs.STACS.2017.9

DO - 10.4230/LIPIcs.STACS.2017.9

M3 - Conference contribution

AN - SCOPUS:85016209904

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017

A2 - Vallee, Brigitte

A2 - Vollmer, Heribert

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017

Y2 - 8 March 2017 through 11 March 2017

ER -