Smallest Enclosing Disk Queries Using Farthest-Point Voronoi Diagrams

Kevin Buchin, Mark Joachim Krallmann, Frank Staals

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-alig…