## Abstract

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.

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 language | English |
---|---|

Pages (from-to) | 191-212 |

Number of pages | 21 |

Journal | Journal of Computational Geometry |

Volume | 9 |

Issue number | 1 |

DOIs | |

Publication status | Published - 2018 |