Computational aspects of disks enclosing many points
Abstract
Let $S$ be a set of $n$ points in the plane. We present several different algorithms for finding a pair of points in $S$ such that any disk that contains that pair must contain at least $cn$ points of $S$, for some constant $c>0$. The first is a randomized algorithm that finds a pair in $O(n\log n)$ expected time for points in general position, and $c = 1/2-\sqrt{(1+2α)/12}$, for any $0
Fields of Study & Subjects
Computational Geometry and Mesh Generation
Complexity and Algorithms in Graphs
Advanced Combinatorial Mathematics
Publication details
- Journal / source
- arXiv (Cornell University)
- Publication date
- 27 January 2026
- Document type
- Preprint