Abstract
Given a point set P in 2D, the problem of finding the smallest set of unit disks that cover all of P is NP-hard. We present a simple algorithm for this problem with an approximation factor of 25/6 in the Euclidean norm and 2 in the max norm, by restricting the disk centers to lie on parallel lines. The run time and space of this algorithm is O(n log n) and O(n) respectively. This algorithm extends to any Lp norm and is asymptotically faster than known alternative approximation algorithms for the same approximation factor.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.