Output sensitive algorithm for covering many points

A set of points and a positive integer $m$ are given and our goal is to cover the maximum number of these point with $m$ disks. We devise the first output sensitive algorithm for this problem. We introduce a parameter $\rho$ as the maximum number of points that one disk can cover. In this paper first we solve the problem for $m=2$ in $O({n\rho} + {\rho ^3}\log \rho ))$ time. The previous algorithm for this problem runs in $O({n^3}\log n)$ time. Our algorithm outperforms the previous algorithm because $\rho$ is much smaller than $n$ in many cases. Then we extend the algorithm for any value of $m$ and we solve the problem in $O(m{n\rho} + {(m\rho )^{2m - 1}}\log m\rho )$ time. The previous algorithm for this problem runs in $O({n^{2m - 1}}\log n)$ time. Our algorithm runs faster than the previous algorithm because $m\rho$ is smaller than $n$ in many cases. Our technique to obtain an output sensitive algorithm is to use a greedy algorithm to confine the areas that we should search to obtain the result. Our technique in this paper may be applicable in other set covering problems that deploy a greedy algorithm, to obtain faster solutions.


Introduction
In the classic covering problem, a set of points are given, and the goal is to place the minimum number of unit disks to cover all the input points. In the maximum coverage problem, the number of disks to be used, m, is given and the goal is to cover the maximum number of points with m disks. We call this problem M ostP oints(P, m). This problem was introduced by Drezner [1] for m = 1 and it was solved in O(n 2 log n) time. To solve the problem, he replaced every point with a disk centered at that point and he obtained the maximum depth in the arrangement of disks. Later, Chazelle and Lee [2] solved the problem in O(n 2 ) time. This problem belongs to the 3-SUM hard complexity class [3], which means that, the O(n 2 ) running time algorithm is the best one for this problem. However, there are some algorithms which approximately solve this problem in less than O(n 2 ) time. These algorithms approximate the disk radius and the number of covered points. Figueiredo and Fonesca [5] gave an algorithm to cover the maximum number of points that a unit disk in d can cover, with a (1 + ε)-radius disk in O(n/ε d−1 ) time. In [4] Aronov and Har-peled gave a (1 − ε)-approximation algorithm in the number of covered points which runs in O(nε −2 log n) time. M ostP oints(P, m), for m > 1, is NP-Hard unless we consider m as a constant. A trivial greedy algorithm is a (1 − 1 e )-approximation algorithm for it [6]. The greedy algorithm first finds a disk which covers the maximum number of points in O(n 2 ) time. To pick the next disks, it removes the points located in the first disk, and finds the disk which covers the maximum total weight of points as the second disk. It repeats this process until m disks are picked up. This yields a (1 − 1 e )-approximation algorithm which runs in O(mn 2 ) time. The first (1 − ε)approximation algorithm for this problem was given in [7] which runs in O(n log n + nε −6m+6 log( 1 ε )) time. We presented a polynomial time approximation schema for this problem in our previous work [8], The trivial method to obtain the optimal result of the M ostP oints(P, m) is to consider all subsets of size m of n 2 possible disks and finds the subset which covers the most number of points. This method takes O(n 2m ) time. In [7] de Berg et. al gave an algorithm for this problem. They first solved the problem for m = 2 in O(n 3 log n) time. To solve the problem for m > 2, they fixed every subset of m − 2 disks, and they found the best 2 disks after removing the points contained in the m − 2 disks. This takes O(n 2m−1 log n) time.
In section 2, we present an output sensitive algorithm to obtain the optimal result of M ostP oints(P, 2) which runs in O(nρ + ρ 3 log ρ) time where ρ is the maximum number of points that one disk can cover. In Section 3 we extends the algorithm for M ostP oints(P, m) . In section 4 we compare the implementation results of our algorithm and the algorithm of [7] and in section 5 we conclude the paper. Our innovation in this algorithm is to use the greedy algorithm to find the regions in which the m resultant disks may reside, and searching in those regions only. In the rest of the paper when we use disks we mean unit disks.

Output sensitive algorithm for MostPoints(P,2)
In this section we describe our algorithm for M ostP oints(P, 2). Let g 1 = M ostP oints(P, 1) be the disk that covers the maximum number points from the point set P . Let P oints(g 1 ) refers to the points of P which are located inside g 1 . Define g 2 = M ostP oints(P − P oints(g 1 ), 1) as the disk that covers the maximum number of points after removing the points located in g 1 . g 1 and g 2 are the result of the greedy algorithm for M ostP oints(P, 2). An example is given in Figure 1. In this example, the optimal solution covers 18 points whereas the greedy algorithm covers 15 points. As illustrated in this example, the two disks of the optimal solution have common points with g 1 . Intuitively, either the disks of the optimal solution have common points with g 1 or, the greedy algorithm obtains the optimal solution. Lemma 1 proves this claim. By the best two disks we mean the optimal solution of M ostP oints(P, 2). Let D be a set of disks. The function Cover(D) denotes the number of points covered by the disks in D.
Lemma 1: Let g 1 be one of the disks that covers the maximum number of points and g 2 be one of the disks that covers the maximum number of points after removing the points located in g 1 . Let o 1 and o 2 be the two disks that together cover the maximum number of points among any combination of two disks: Either both o 1 and o 2 have common points with g 1 , or g 1 and g 2 cover the maximum number of points.
Proof: Suppose that at least one of o 1 and o 2 , say o 2 , does not have any common point with g 1 . Then we have Cover({g 1 , g 2 }) ≥ Cover({g 1 , o 2 }), because g 2 covers the maximum number of points not In this example, the greedy algorithm returns g1 and g2 which cover 15 points together, whereas the disks in the optimal solution, the two disks specified with the dash lines, cover 18 points together. covered by g 1 . We also have Cover({g 1 , o 2 }) ≥ Cover({o 1 , o 2 }) because g 1 covers at least the same weight of points as o 1 (since it is a disk that covers the maximum weight of points) and g 1 does not have any point in common with o 2 . Thus Cover({g 1 , g 2 }) ≥ Cover({o 1 , o 2 }), which implies that the total number of the points covered by g 1 and g 2 is maximal. 2 Based on Lemma 1, we should look for the best two disks in the disks which have common points with g 1 . These disks are located around g 1 in a circle having the same center as g 1 and radius 3, where the radius of g 1 is 1. We call this region N g 1 . Figure 2 shows N g 1 . Lemma 2 bounds the number of points in N g 1 .
Lemma 2: Let ρ be the maximum number of points that can be covered by a disk. The number of points in N g 1 is O(ρ).
Proof: We can pack N g 1 with at most 21 unit disks, which is shown in Figure 3. Every one of these 21 disks covers equal or less than ρ points. So the number of points in N g 1 is at most 21ρ points, which is O(ρ) points. 2 We can also devise an output sensitive algorithm for M ostP oints(P, 1) that solves the problem in O(nρ) time. The algorithm is as follows. Cover the plane using four shifted grids G 1 , ..., G 4 . Each grid covers the whole plane, but the grids are shifted relative to each other, 2 units from each side. The cells of the grids have size 4x4. For any unit disk d there is a grid G i such that d is fully contained in a single cell of G i . Now, for each non-empty grid cell C of every grid, compute the optimal disk on the set of points lying inside C. C contains at most cρ points, for a constant value of c and the time spent for cell C is O(|C| 2 ) where |C| denotes the number of points in the cell. The total number of points over all cells C is 4n, since each point is contained in exactly one cell per grid. To obtain the running time of the algorithm, we count the cells of the grids C 1 , ..., C l . The total running time of the algorithm is: Using Lemma 1 and Lemma 2, the best two disks can be g 1 and g 2 , or the two disks around g 1 that cover the maximum number of points. To find the best two disks in P , first we find g 1 and g 2 in O(nρ) time. Then, we determine the points in N g 1 , and we run the algorithm of [7] for the points located in N g 1 . This algorithm obtains the best two disks in N g 1 , in O(ρ 3 log ρ) time. Finally, we compare this result, the best two disks in N g 1 , with g 1 and g 2 and consider the one that covers more weight as the optimal solution for M ostP oints(P, 2). Since ρ can be much smaller than n in practice, our algorithm which runs in O(nρ + ρ 3 log ρ) time, is an improvement over the algorithm of [7] that requires O(n 3 log n) time.

The algorithm for MostPoints(P,m)
The algorithm can be extended to cover the maximum number of points with m disks. From now on, by the best j disks, we mean a set of j disks that cover the maximum total weight of points. The proposed algorithm is an iterative algorithm. At the first iteration, the algorithm finds two disks, which cover the maximum number of points as explained before. To find the best 3 disks, the algorithm uses the following fact, which will be proven in Lemma 3: the best 3 disks are among the disks that have some common points with the best 2 disks; Otherwise, the best 2 disks plus one disk that covers the maximum number of points, after removing the points located in the best two disks, are the best 3 disks. The algorithm repeats this process until the best m disks are found. Now we explain the algorithm formally. Remember that the function M ostP oints(Q, j) returns a set of j disks that cover the maximum number of points in the point set Q. Let D be a set of unit disks. Define P oints(D) = {p|p ∈ (P ∩ D)} as the subset of P that is located in the disks of D. Define N eighbor(D) as the points in the circles with the same centers as the disks in D and radius 3. Let OP T i denotes the best i disks. The outline of the algorithm is as follows: The exact output sensitive algorithm for the most points covering problem Inputs: A set P of n points in the plane, and a positive integer m. Outputs: A set of m disks which cover the maximum number of points from P. Definitions: The function MostPoints(Q,j), Points(D), and Neighbor(D) as defined in the text.

end
In Lemma 3 we prove the correctness of the above algorithm. Before proving Lemma 3 we have the following definitions. Proof: We prove the correctness of the algorithm by induction on the number of iterations. Assume that at the end of iteration i we have correctly computed OP T i . Consider OP T i+1 , which consists of i + 1 disks. These disks may have common points with P oints(OP T i ) or not. We consider both cases. In case 1 we consider that all i + 1 disks of OP T i+1 have common points with P oints(OP T i ), and in case 2 we consider that some of these i disks do not have any common point with P oints(OP T i ).
Case1: All i + 1 disks of OP T i+1 have common points with P oints(OP T i ): All disks that have common points with P oints(OP T i ), have some points in N eighbor(OP T i ). The algorithm, in line 8, obtains the best i + 1 disks in the points of N eighbor(OP T i ). So in this case the algorithm exactly computes OP T i+1 .
Case 2: Some of the disks in OP T i+1 do not have any common point with P oints(OP T i ): Call one of these disks F . We can partition OP T i+1 to {OP T i+1 − F } and F . Based on the Definition 1, we have: As OP T i is a set of i disks which cover the maximum number of points, we have: Furthermore, g i+1 is the disk that covers the maximum number of points after removing the points in P oints(OP T i ). Therefore, g i+1 covers the maximum number of points among the disks that have not common points with OP T i . Thus, we have: From (2) and (3) we have: From (1) and (4) we have: Thus in case 2, OP T i and g i+1 cover the maximum number of points. The algorithm compares the results of case 1 with the result of case 2, and considers the best one as OP T i+1 . So, the algorithm correctly computes OP T i+1 . The base case, i = 1, is correct and can be satisfied using the algorithm devised for M ostP oints(P, 1). 2 In the following lemma, we obtain the running time of the algorithm. Lemma 4: The exact output sensitive algorithm for the most points covering problem runs in O(mnρ+ (mρ) 2m−1 log mρ) time, where ρ is the maximum number of points that one disk can cover in the points set P .

Proof:
The algorithm runs in m iterations. At the start of the iteration i, we have found the best i − 1 disks, and we are getting to find the best i disks. To find the best i disks, we obtain g i in line 7, which takes O(nρ) time. We also look for the i disks covering the maximum number of points in N eighbor(OP T i−1 ), in line 8. N eighbor(OP T i−1 ) consists of i − 1 disks, and based on Lemma 2, the neighborhood of each disk can be packed with at most 21 disks. So the maximum number of points in N eighbor(OP T i−1 ) is 21ρ(i−1), which is O(iρ) points. We search for the i disks that cover the maximum number of points in O(iρ) points. The algorithm of [7] is applied for these points, which takes O((iρ) 2i−1 log(iρ)) time. The algorithm runs in m iterations so, the running time is bounded by O(nρ) + m i=2 (O(nρ) + (iρ) 2i−1 log(mρ)) which is O(mnρ + (mρ) 2m−1 log(mρ)). 2

Implementation results
We have implemented our algorithm and the algorithm of [7] for M ostP oints(P, 2). In each algorithm, we observed the number of pairs of disks that each algorithms consider to obtain the optimal solution. We distributed different number of points randomly in squares with different side length and we run both algorithms on the points. Table 1 shows the result of the comparison. The results show that our algorithm computes significantly less number of pairs than the algorithm of [7] in most cases. When ρ n becomes close to 1, the number of pair of disks that are considered in both algorithms become close to each other.

Extending the algorithm for other shapes and weighted point sets
This algorithm can be applied for other types of maximum coverage problem such as covering point sets with other shapes and maximum coverage problem in sets. The algorithm uses the parameter ρ which is Tab. 1: Number of pairs of disks processed in our algorithm an algorithm of [7] Num of points square side ρ Num of pairs in algorithm of [7] Num of pairs in our algorithm  1000  200  19  7007  201  1000  100  44  22878  1131  1000  50  125 45414  4259  500  50  105 26041  6402  500  100  34  8605  252 the cardinality of the largest subset. Lemma 1 and 3 can be applied for general set systems. So we should search in the subsets that have common members with the largest subsets. To bound the running time of the algorithm there should be a constant number of subsets that have common points with the largest subsets.

Conclusion and future works
In this paper we presented an exact output sensitive algorithm for covering many points problem. In the algorithm, we confined the region in which the resultant disks may reside using the greedy algorithm, and we searched in that regions only. This led to an output sensitive algorithm for this problem which runs in O(mnρ + (mρ) 2m−1 log mρ) time, where ρ is the maximum number of points that one disk can cover. Our algorithm can be improved by improving the running time of the algorithm in [7]. If better algorithms for covering most points with two disks are suggested, they can improve the running time of our algorithm and the algorithm of [7]. Furthermore, considering ρ as a parameter, and using our technique, it may be possible to improve the analysis of other covering algorithms.