Time-Space Trade-os for Voronoi Diagrams
Matias Korman, Wolfgang Mulzer, Marcel Roelo, Paul Seiferth, Yannik Stein · 2015
Let S be a planar n-point set. Classically, one can nd the Voronoi diagram VD( S) for S in O(n logn) time and O(n) space. We study the situation when the available workspace is limited: for s2f1;:::;ng, 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. We describe a randomized s-workspace algorithm for nding VD( S) in expected time O((n 2 =s) logs + n logs log s). This almost matches the optimal running times for both constant and linear workspace and provides a continuous trade-o between them.