Improved time-space trade-offs for computing Voronoi diagrams

Bahareh Banyassady, Matias Korman, Wolfgang Mulzer, A.M. van Renssen, Marcel Roeloffzen, Paul Seiferth, Yannik Stein

Research output: Contribution to journalArticleAcademicpeer-review

91 Downloads (Pure)


Let $P$ be a planar set of $n$ \emph{sites} in general position.For $k \in \{1, \dots, n-1\}$, the Voronoi diagram\emph{of order $k$} for $P$ is obtained by subdividing the plane into\emph{cells} such that points in the same cell have the sameset of nearest $k$ neighbors in $P$.The \emph{\textup{(}nearest site\textup{)} Voronoi diagram} ($\NVD$) andthe\emph{farthest site Voronoi diagram} ($\FVD$) are the particular casesof $k=1$ and $k=n-1$, respectively. For any given $K \in \{1, \dots,n-1\}$, the family of all higher-order Voronoi diagrams of order$k = 1, \dots, K$ for $P$ can be computed in total time $O(nK^2+ n\log n)$ using $O(K^2(n-K))$ space [Aggarwal \etal, DCG'89; Lee, TC'82].Moreover, $\NVD$ and $\FVD$ for $P$ can be computed in $O(n\log n)$time using $O(n)$ space [Preparata, Shamos, Springer'85].
For $s \in \{1, \dots, n\}$, an \emph{$s$-workspace} algorithm hasrandom access to a read-only array with the sites of $P$ in arbitraryorder.  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 ormodified afterwards.
We describe a deterministic $s$-workspace algorithm for computing$\NVD$ and $\FVD$ for $P$ that runs in $O((n^2/s)\log s)$time. Moreover, we generalize our $s$-workspacealgorithm so that for any given $K \in O(\sqrt{s})$,we compute the family of all higher-order Voronoi diagramsof order $k = 1, \dots, K$ for $P$ in total expected time$O\bigl(\frac{n^2 K^5}{s}(\log s + K \, 2^{O(\log^* K)}) \bigr)$ orin total deterministic time$O\bigl(\frac{n^2 K^5}{s}(\log s + K \log K) \bigr)$.Previously, for Voronoi diagrams, the only known $s$-workspacealgorithm runs in \emph{expected} time$O\bigl((n^2/s) \log s + n \log s \log^*s\bigr)$ [Korman \etal, WADS'15]and only works for $\NVD$ (i.e., $k=1$). Unlike the previousalgorithm, our new method is very simple and does not rely onadvanced data structures or random sampling techniques.
Original languageEnglish
Pages (from-to)191-212
Number of pages21
JournalJournal of Computational Geometry
Issue number1
Publication statusPublished - 2018


Dive into the research topics of 'Improved time-space trade-offs for computing Voronoi diagrams'. Together they form a unique fingerprint.

Cite this