Smallest Enclosing Disk Queries Using Farthest-Point Voronoi Diagrams
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909014297673728 |
|---|---|
| author | Buchin, Kevin Krallmann, Mark Joachim Staals, Frank |
| author_facet | Buchin, Kevin Krallmann, Mark Joachim Staals, Frank |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_00743 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Smallest Enclosing Disk Queries Using Farthest-Point Voronoi Diagrams Buchin, Kevin Krallmann, Mark Joachim Staals, Frank Computational Geometry Data Structures and Algorithms F.2.2 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. |
| title | Smallest Enclosing Disk Queries Using Farthest-Point Voronoi Diagrams |
| topic | Computational Geometry Data Structures and Algorithms F.2.2 |
| url | https://arxiv.org/abs/2605.00743 |