Algorithms for Minimizing the Movements of Spreading Points in Linear Domains
Shimin Li, Wang, Haitao · DOAJ (DOAJ: Directory of Open Access Journals) · 2022
We study a problem on spreading points. Given a set P of n points sorted on a line L and a distance value δ we wish to move the points of P along L such that the distance of any two points of P is at least δ and the maximum movement over all points of P is minimized. Using the greedy strategy, we present an O(n) time algorithm for this problem. Further, we extend our algorithm to solve (in O(n) time) the cycle version of the problem where all points of P are on a cycle C. Previously, only weakly polynomial-time algorithms were known for these problems based on linear programming (of n variables and Θ(n) constraints). In addition, we present a linear-time algorithm for another similar facility-location moving problem, which improves on previous work.