Smallest Enclosing Disk Queries Using Farthest-Point Voronoi Diagrams
This work provides a simpler and faster solution for a fundamental geometric query problem, benefiting computational geometry applications.
The authors present a new data structure for answering smallest enclosing disk queries under axis-aligned rectangles, achieving deterministic query time O(log^4 n) and randomized expected query time O(log^{5/2} n log log n) with O(n log^2 n) preprocessing, improving over previous O(log^6 n) query time.
Let $S$ be a set of $n$ points in $\mathbb{R}^2$. Our goal is to preprocess $S$ to efficiently compute the smallest enclosing disk of the points in $S$ that lie inside an axis-aligned query rectangle. Previous data structures for this problem achieve a query time of $O(\log^6 n)$ with $O(n \log^2 n)$ preprocessing time and space by lifting the points to 3D, dualizing them into polyhedra, and searching through their intersections. We present a significantly simpler approach, solely based on 2D geometric structures, specifically 2D farthest-point Voronoi diagrams. Our approach achieves a deterministic query time of $O(\log^4 n)$ and, via randomization, an expected query time of $O(\log^{5/2} n \log\log n)$ with the same preprocessing bounds.