
arXiv: 1312.0389
Discrete Algorithms 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.
Computational Geometry (cs.CG), FOS: Computer and information sciences, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], covering with disks, [info.info-hc] computer science [cs]/human-computer interaction [cs.hc], QA1-939, computational geometry, [info.info-dm] computer science [cs]/discrete mathematics [cs.dm], Computer Science - Computational Geometry, output sensitive algorithm, [INFO.INFO-HC] Computer Science [cs]/Human-Computer Interaction [cs.HC], Mathematics
Computational Geometry (cs.CG), FOS: Computer and information sciences, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], covering with disks, [info.info-hc] computer science [cs]/human-computer interaction [cs.hc], QA1-939, computational geometry, [info.info-dm] computer science [cs]/discrete mathematics [cs.dm], Computer Science - Computational Geometry, output sensitive algorithm, [INFO.INFO-HC] Computer Science [cs]/Human-Computer Interaction [cs.HC], Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
