Improved time-space trade-offs for computing Voronoi diagrams

Abstract

Let P be a planar set of n sites in general position. For k∈{1,…,n−1}, the Voronoi diagram of order k for P is obtained by subdividing the plane into cells such that points in the same cell have the same set of nearest k neighbors in P. The (nearest site) Voronoi diagram (NVD) and the farthest site Voronoi diagram (FVD) are the particular cases of k=1 and k=n−1, respectively. For any given K∈{1,…,n−1}, the family of all higher-order Voronoi diagrams of order k=1,…,K for P can be computed in total time O(nK2+nlogn) using O(K2(n−K)) space [Aggarwal et al., DCG'89; Lee, TC'82]. Moreover, NVD and FVD for P can be computed in O(nlogn) time using O(n)

space [Preparata, Shamos, Springer'85].

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 or modified afterwards.

We describe a deterministic s -workspace algorithm for computing NVD and FVD for P that runs in O((n2/s)logs) time. Moreover, we generalize our s-workspace algorithm so that for any given K∈O(s√), we compute the family of all higher-order Voronoi diagrams of order k=1,…,K for P in total expected time O(n2K5s(logs+K2O(log∗K))) or in total deterministic time O(n2K5s(logs+KlogK)). Previously, for Voronoi diagrams, the only known s-workspace algorithm runs in expected time O((n2/s)logs+nlogslog∗s) [Korman et al., WADS'15] and only works for NVD (i.e., k=1). Unlike the previous algorithm, our new method is very simple and does not rely on advanced data structures or random sampling techniques.