A Couple of Simple Algorithms for $k$-Dispersion
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915592166965248 |
|---|---|
| author | Chen, Ke Dumitrescu, Adrian |
| author_facet | Chen, Ke Dumitrescu, Adrian |
| contents | Given a set $P$ of $n$ points in $\mathbf{R}^d$, and a positive integer $k \leq n$, the $k$-dispersion problem is that of selecting $k$ of the given points so that the minimum inter-point distance among them is maximized (under Euclidean distances). Among others, we show the following:
(I) Given a set $P$ of $n$ points in the plane, and a positive integer $k \geq 2$, the $k$-dispersion problem can be solved by an algorithm running in $O\left(n^{k-1} \log{n}\right)$ time. This extends an earlier result for $k=3$, due to Horiyama, Nakano, Saitoh, Suetsugu, Suzuki, Uehara, Uno, and Wasa (2021) to arbitrary $k$. In particular, it improves on previous running times for small $k$.
(II) Given a set $P$ of $n$ points in $\mathbf{R}^3$, and a positive integer $k \geq 2$, the $k$-dispersion problem can be solved by an algorithm running in $O\left(n^{k-1} \log{n}\right)$ time, if $k$ is even; and $O\left(n^{k-1} \log^2{n}\right)$ time, if $k$ is odd. For $k \geq 4$, no combinatorial algorithm running in $o(n^k)$ time was known for this problem.
(III) Let $P$ be a set of $n$ random points uniformly distributed in $[0,1]^2$. Then under suitable conditions, a $0.99$-approximation for $k$-dispersion can be computed in $O(n)$ time with high probability. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_00692 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Couple of Simple Algorithms for $k$-Dispersion Chen, Ke Dumitrescu, Adrian Computational Geometry Discrete Mathematics Metric Geometry Given a set $P$ of $n$ points in $\mathbf{R}^d$, and a positive integer $k \leq n$, the $k$-dispersion problem is that of selecting $k$ of the given points so that the minimum inter-point distance among them is maximized (under Euclidean distances). Among others, we show the following: (I) Given a set $P$ of $n$ points in the plane, and a positive integer $k \geq 2$, the $k$-dispersion problem can be solved by an algorithm running in $O\left(n^{k-1} \log{n}\right)$ time. This extends an earlier result for $k=3$, due to Horiyama, Nakano, Saitoh, Suetsugu, Suzuki, Uehara, Uno, and Wasa (2021) to arbitrary $k$. In particular, it improves on previous running times for small $k$. (II) Given a set $P$ of $n$ points in $\mathbf{R}^3$, and a positive integer $k \geq 2$, the $k$-dispersion problem can be solved by an algorithm running in $O\left(n^{k-1} \log{n}\right)$ time, if $k$ is even; and $O\left(n^{k-1} \log^2{n}\right)$ time, if $k$ is odd. For $k \geq 4$, no combinatorial algorithm running in $o(n^k)$ time was known for this problem. (III) Let $P$ be a set of $n$ random points uniformly distributed in $[0,1]^2$. Then under suitable conditions, a $0.99$-approximation for $k$-dispersion can be computed in $O(n)$ time with high probability. |
| title | A Couple of Simple Algorithms for $k$-Dispersion |
| topic | Computational Geometry Discrete Mathematics Metric Geometry |
| url | https://arxiv.org/abs/2511.00692 |