Banyassady, Bahareh ;
Korman, Matias ;
Mulzer, Wolfgang ;
van Renssen, André ;
Roeloffzen, Marcel ;
Seiferth, Paul ;
Stein, Yannik
Improved TimeSpace TradeOffs for Computing Voronoi Diagrams
Abstract
Let P be a planar npoint set in general position. For k between 1 and n1, 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=n1, respectively. It is known that the family of all higherorder Voronoi diagrams of order 1 to K for P can be computed in total time O(n K^2 + n log n) using O(K^2(nK)) space. Also NVD and FVD can be computed in O(n log n) time using O(n) space.
For s in {1, ..., n}, an sworkspace algorithm has random access to a readonly array with the sites of P in arbitrary order. Additionally, the algorithm may use O(s) words of Theta(log n) bits each for reading and writing intermediate data. The output can be written only once and cannot be accessed afterwards.
We describe a deterministic sworkspace algorithm for computing an NVD and also an FVD for P that runs in O((n^2/s) log s) time. Moreover, we generalize our sworkspace algorithm for computing the family of all higherorder Voronoi diagrams of P up to order K in O(sqrt(s)) in total time O( (n^2 K^6 / s) log^(1+epsilon)(K) (log s / log K)^(O(1)) ) for any fixed epsilon > 0. Previously, for Voronoi diagrams, the only known sworkspace algorithm was to find an NVD for P in expected time O((n^2/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.
BibTeX  Entry
@InProceedings{banyassady_et_al:LIPIcs:2017:7024,
author = {Bahareh Banyassady and Matias Korman and Wolfgang Mulzer and Andr{\'e} van Renssen and Marcel Roeloffzen and Paul Seiferth and Yannik Stein},
title = {{Improved TimeSpace TradeOffs for Computing Voronoi Diagrams}},
booktitle = {34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
pages = {9:19:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770286},
ISSN = {18688969},
year = {2017},
volume = {66},
editor = {Heribert Vollmer and Brigitte Vallée},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7024},
URN = {urn:nbn:de:0030drops70249},
doi = {10.4230/LIPIcs.STACS.2017.9},
annote = {Keywords: memoryconstrained model, Voronoi diagram, timespace tradeoff}
}
2017
Keywords: 

memoryconstrained model, Voronoi diagram, timespace tradeoff 
Seminar: 

34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Issue date: 

2017 
Date of publication: 

2017 