DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2026.124

Smallest Enclosing Disk Queries Using Farthest-Point Voronoi Diagrams

Authors: Kevin Buchin, Mark Joachim Krallmann, and Frank Staals

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract

Let S be a set of n points in R². 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⁶ n) with O(n log² 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⁴ n) and, via randomization, an expected query time of O(log^{5/2} n log log n) with the same preprocessing bounds.

Cite as

Kevin Buchin, Mark Joachim Krallmann, and Frank Staals. Smallest Enclosing Disk Queries Using Farthest-Point Voronoi Diagrams. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 124:1-124:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.ESA.2026.124,
  author =	{Buchin, Kevin and Krallmann, Mark Joachim and Staals, Frank},
  title =	{{Smallest Enclosing Disk Queries Using Farthest-Point Voronoi Diagrams}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{124:1--124:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.124},
  URN =		{urn:nbn:de:0030-drops-272608},
  doi =		{10.4230/LIPIcs.ESA.2026.124},
  annote =	{Keywords: Range searching, smallest enclosing disk, farthest point Voronoi diagram}
}

Search Results

Documents authored by Krallmann, Mark Joachim

Smallest Enclosing Disk Queries Using Farthest-Point Voronoi Diagrams

Abstract

Cite as

Thanks for your feedback!

Could not send message