Dispersing points on intervals

作者：Li Shimin^*; Wang Haitao

来源：Discrete Applied Mathematics, 2018, 239: 106-118.

DOI：10.1016/j.dam.2017.12.028

• Dispersing points
• Intervals
• Lines
• Cycles
• Algorithms

We consider a problem of dispersing points on disjoint intervals on a line. Given n pairwise disjoint intervals sorted on a line, we want to find a point in each interval such that the minimum pairwise distance of these points is maximized. Based on a greedy strategy, we present a linear time algorithm for the problem. Further, we also solve in linear time the cycle version of the problem where the intervals are given on a cycle.

• 出版日期2018-4-20