2025/11/01 by Chen, Ke, Dumitrescu, Adrian
#Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Metric Geometry (math.MG)
paper · doi:10.48550/arxiv.2511.00692
Given a set P of n points in Rd, and a positive integer 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: (I) Given a set P of n points in the plane, and a positive integer k ≥ 2, the k-dispersion problem can be solved by an algorithm running in O(nk-1 logn) 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 R3, and a positive integer k ≥ 2, the k-dispersion problem can be solved by an algorithm running in O(nk-1 logn) time, if k is even; and O(nk-1 log2n) time, if k is odd. For k ≥ 4, no combinatorial algorithm running in o(nk) 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.