Smallest Enclosing Disk Queries Using Farthest-Point Voronoi Diagrams

Abstract

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.

22 pages, 20 figures. Presented at ESA 2026