Given a set of n disjoint intervals on a line and an integer k, we want to find k points in the intervals so that the minimum pairwise distance of the k points is maximized. Intuitively, given a set of n disjoint time intervals on a timeline, each of which is a time span we are allowed to check something, and an integer k, which is the number of times we will check something, we plan k checking times so that the checks occur at equal time intervals as much as possible, that is, we want to maximize the minimum time interval between the k checking times. We call the problem the k-dispersion problem on intervals. If we need to choose exactly one point in each interval, so k=n, and the disjoint intervals are given in the sorted order on the line, then two O(n) time algorithms to solve the problem are known. In this paper we give the first O(n) time algorithm to solve the problem for any constant k. Our algorithm works even if the disjoint intervals are given in any (not sorted) order. If the disjoint intervals are given in the sorted order on the line, then, by slightly modifying the algorithm, one can solve the problem in O(log n) time. This is the first sublinear time algorithm to solve the problem. Also we show some results on the k-dispersion problem on disks, including an FPTAS.

Given a set P of n points and an integer k, we wish to place k facilities on points in P so that the minimum distance between facilities is maximized. The problem is called the k-dispersion problem, and the set of such k points is called a k-dispersion of P. Note that the 2-dispersion problem corresponds to the computation of the diameter of P. Thus, the k-dispersion problem is a natural generalization of the diameter problem. In this paper, we consider the case of k=3, which is the 3-dispersion problem, when P is in convex position. We present an O(n2)-time algorithm to compute a 3-dispersion of P.

Given a set P of n points on which facilities can be placed and an integer k, we want to place k facilities on some points so that the minimum distance between facilities is maximized. The problem is called the k-dispersion problem. In this paper, we consider the 3-dispersion problem when P is a set of points on a plane (2-dimensional space). Note that the 2-dispersion problem corresponds to the diameter problem. We give an O(n) time algorithm to solve the 3-dispersion problem in the L∞ metric, and an O(n) time algorithm to solve the 3-dispersion problem in the L1 metric. Also, we give an O(n2 log n) time algorithm to solve the 3-dispersion problem in the L2 metric.

The dispersion problem is a variant of the facility location problem. Given a set P of n points and an integer k, we intend to find a subset S of P with |S|=k such that the cost minp∈S{cost(p)} is maximized, where cost(p) is the sum of the distances from p to the nearest c points in S. We call the problem the dispersion problem with partial c sum cost, or the PcS-dispersion problem. In this paper we present two algorithms to solve the P2S-dispersion problem(c=2) if all points of P are on a line. The running times of the algorithms are O(kn2 log n) and O(n log n), respectively. We also present an algorithm to solve the PcS-dispersion problem if all points of P are on a line. The running time of the algorithm is O(knc+1).

Let P be a set of points on the plane, and d(p, q) be the distance between a pair of points p, q in P. For a point p∈P and a subset S ⊂ P with |S|≥3, the 2-dispersion cost, denoted by cost2(p, S), of p with respect to S is the sum of (1) the distance from p to the nearest point in Ssetminus{p} and (2) the distance from p to the second nearest point in Ssetminus{p}. The 2-dispersion cost cost2(S) of S ⊂ P with |S|≥3 is minp∈S{cost2(p, S)}. Given a set P of n points and an integer k we wish to compute k point subset S of P with maximum cost2(S). In this paper we give a simple 1/({4sqrt{3}}) approximation algorithm for the problem.