2013/12/02 by Hossein Ghasemalizadeh, Ghasemalizadeh, Hossein, Mohammadreza Razzazi +1
Computer Science · #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Optimization and Search Problems #cs.CG
paper · pdf · doi:10.48550/arxiv.1312.0389
9 Pages, 3 figures
arxiv created 2013/12/02 · openalex publication_date 2013/12/02 · arxiv updated 2013/12/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ρ 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ρ + ρ3log ρ)) time. The previous algorithm for this problem runs in O(n3log n) time. Our algorithm outperforms the previous algorithm because ρ 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(mnρ + (mρ)2m - 1log mρ) time. The previous algorithm for this problem runs in O(n2m - 1log n) time. Our algorithm runs faster than the previous algorithm because mρ 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.