Acta Informatica Компьютерные сети и коммуникации

A couple of simple algorithms for k-dispersion

Ke Chen, Adrian Dumitrescu
Springer Nature · 2026-06-16 · DOI 10.1007/s00236-026-00534-1

Аннотация

Abstract Given a set P of n points in $$\mathbb {R}^d$$ R d , and a positive integer $$k \le n$$ k ≤ 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: Given a set P of n points in the plane, and a positive integer $$k \ge 2$$ k ≥ 2 , the k -dispersion problem can be solved by an algorithm running in $$O\left( n^{k-1} \log {n}\right) $$ O n k - 1 log n time. This extends an earlier result for $$k=3$$ k = 3 , due to Horiyama, Nakano, Saitoh, Suetsugu, Suzuki, Uehara, Uno, and Wasa [20] to arbitrary k . In particular, it improves on previous running times for small k . Given a set P of n points in $$\mathbb {R}^3$$ R 3 , and a positive integer $$k \ge 2$$ k ≥ 2 , the k -dispersion problem can be solved by an algorithm running in $$ {\left\{ \begin{array}{ll} O\left( n^{k-1} \log {n}\right) \text {time}, & \text {if } k \text { is even};\\ O\left( n^{k-1} \log ^2{n}\right) \text {time}, & \text {if } k \text { is odd}. \end{array}\right. } $$ O n k - 1 log n time , if k is even ; O n k - 1 log 2 n time , if k is odd . For $$k \ge 4$$ k ≥ 4 , no combinatorial algorithm running in $$o(n^k)$$ o ( n k ) time was known for this problem. Let P be a set of n random points uniformly distributed in $$[0,1]^2$$ [ 0 , 1 ] 2 . Then under suitable conditions, a 0.99-approximation for k -dispersion can be computed in O ( n ) time with high probability.

Читать у издателя →