p-centers on a Line | Algorithms Notes
Given a set S of n points on a line and a positive integer p, design an algorithm to find a set F of p points in the line such that the maximum distance from all points point in S to F is minimized.
Solution:
For a fix distance d, we can use linear time algorithm algorithm to test whether d is a feasible maximum distance. Moreover, we only need to find d among half of all distances between pair of points in S. Since the points are on the line, the distances between points are additive. Hence, we don't need to generate all distances to search, but instead we can search the implicit matrix. The time complexity is O(n lg n).
When the points lie on a tree, there is an O(n) time algorithm to cover all points[2]. If we want to cover the whole tree not just points, there is an O(np lg n) method[1].
http://stackoverflow.com/questions/28812174/take-k-elements-and-maximise-the-minimum-distance
http://arxiv.org/pdf/0902.3282.pdf
Read full article from p-centers on a Line | Algorithms Notes
Given a set S of n points on a line and a positive integer p, design an algorithm to find a set F of p points in the line such that the maximum distance from all points point in S to F is minimized.
Solution:
For a fix distance d, we can use linear time algorithm algorithm to test whether d is a feasible maximum distance. Moreover, we only need to find d among half of all distances between pair of points in S. Since the points are on the line, the distances between points are additive. Hence, we don't need to generate all distances to search, but instead we can search the implicit matrix. The time complexity is O(n lg n).
When the points lie on a tree, there is an O(n) time algorithm to cover all points[2]. If we want to cover the whole tree not just points, there is an O(np lg n) method[1].
http://stackoverflow.com/questions/28812174/take-k-elements-and-maximise-the-minimum-distance
http://arxiv.org/pdf/0902.3282.pdf
Read full article from p-centers on a Line | Algorithms Notes
