Computational aspects of disks enclosing many points
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911403701436416 |
|---|---|
| author | Bose, Prosenjit Esteban, Guillermo Tuttle, Tyler |
| author_facet | Bose, Prosenjit Esteban, Guillermo Tuttle, Tyler |
| contents | 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<α<1$. The second algorithm, also for points in general position, takes quadratic time, but the constant $c$ is improved to $1/2-1/{\sqrt{12}} \approx 1/4.7$. The second algorithm can also be used as a subroutine to find the pair that maximizes the number of points inside any disk that contains the pair, in $O(n^2\log n)$ time. We also consider variants of the problem. When the set $S$ is in convex position, we present an algorithm that finds in linear time a pair of points such that any disk through them contains at least $n/3$ points of $ S $. For the variant where we are only interested in finding a pair such that the diametral disk of that pair contains many points, we also have a linear-time algorithm that finds a disk with at least $n/3$ points of $S$. Finally, we present a generalization of the first two algorithms to the case where the set $S$ of points is coloured using two colours. We also consider adapting these algorithms to solve the same problems when $S$ is a set of points inside of a simple polygon $P$, with the notion of a disk replaced by that of a geodesic disk. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_20036 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Computational aspects of disks enclosing many points Bose, Prosenjit Esteban, Guillermo Tuttle, Tyler Computational Geometry 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<α<1$. The second algorithm, also for points in general position, takes quadratic time, but the constant $c$ is improved to $1/2-1/{\sqrt{12}} \approx 1/4.7$. The second algorithm can also be used as a subroutine to find the pair that maximizes the number of points inside any disk that contains the pair, in $O(n^2\log n)$ time. We also consider variants of the problem. When the set $S$ is in convex position, we present an algorithm that finds in linear time a pair of points such that any disk through them contains at least $n/3$ points of $ S $. For the variant where we are only interested in finding a pair such that the diametral disk of that pair contains many points, we also have a linear-time algorithm that finds a disk with at least $n/3$ points of $S$. Finally, we present a generalization of the first two algorithms to the case where the set $S$ of points is coloured using two colours. We also consider adapting these algorithms to solve the same problems when $S$ is a set of points inside of a simple polygon $P$, with the notion of a disk replaced by that of a geodesic disk. |
| title | Computational aspects of disks enclosing many points |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2601.20036 |