Improved Time-Space Trade-offs for Computing Voronoi Diagrams

Let $P$ be a planar set of $n$ sites in general position. For $k\in\{1,\dots,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\in\{1,\dots,n-1\}$, the family of all higher-order Voronoi diagrams of order $...