Output sensitive algorithm for covering many points
Hossein Ghasemalizadeh, Mohammadreza Razzazi
Abstract
In this paper we devise some output sensitive algorithms for a problem
where a set of points and a positive integer, m, are
given and the goal is to cover a maximal number of these points with
m disks. We introduce a parameter, ρ,
as the maximum number of points that one disk can cover and we analyse
the algorithms based on this parameter. At first, we solve the
problem for m=1 in O(nρ) time, which
improves the previous O(n2) time algorithm for
this problem. Then we solve the problem for m=2 in
O(nρ +
3 log ρ) time, which improves the
previous O(n3 log n)
algorithm for this problem. Our algorithms outperform the previous
algorithms because ρ is much smaller than
n in many cases. Finally, we extend the algorithm for
any value of m and solve the problem in O(mnρ + (mρ)2m -
1 log mρ) time. The previous algorithm for this
problem runs in O(n2m -
1 log n) time and our algorithm usually runs faster
than the previous algorithm because mρ is smaller
than n in many cases. We obtain output sensitive
algorithms by confining the areas that we should search for the
result. The techniques used in this paper may be applicable in other
covering problems to obtain faster algorithms.
Full Text: PDF