Back to Search
Start Over
APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS.
- Source :
- International Journal of Computational Geometry & Applications; Dec2013, Vol. 23 Issue 6, p461-477, 17p
- Publication Year :
- 2013
-
Abstract
- In this paper, we consider constant factor approximation algorithms for a variant of the discrete piercing set problem for unit disks. Here a set of points P is given; the objective is to choose minimum number of points in P to pierce the unit disks centered at all the points in P. We first propose a very simple algorithm that produces 12-approximation result in O(n log n) time. Next, we improve the approximation factor to 4 and then to 3. The worst case running time of these algorithms are O(n<superscript>8</superscript> log n) and O(n<superscript>15</superscript> log n) respectively. Apart from the space required for storing the input, the extra work-space requirement for each of these algorithms is O(1). Finally, we propose a PTAS for the same problem. Given a positive integer k, it can produce a solution with performance ratio (1+1/k)<superscript>2</superscript> in n<superscript>O(k)</superscript> time. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 02181959
- Volume :
- 23
- Issue :
- 6
- Database :
- Complementary Index
- Journal :
- International Journal of Computational Geometry & Applications
- Publication Type :
- Academic Journal
- Accession number :
- 97028973
- Full Text :
- https://doi.org/10.1142/S021819591350009X