TY - JOUR

T1 - Covering many or few points with unit disks

AU - de Berg, Mark

AU - Cabello, Sergio

AU - Har-Peled, Sariel

N1 - Funding Information:
Acknowledgements M. de Berg was supported by the Netherland’s Organisation for Scientific Research (NWO) under project No. 639.023.301. S. Cabello was partially supported by the European Community Sixth Framework Programme under a Marie Curie Intra-European Fellowship, and by the Slovenian Research Agency, project J1-7218.

PY - 2009/7

Y1 - 2009/7

N2 - Let P be a set of n weighted points. We study approximation algorithms for the following two continuous facility-location problems.In the first problem we want to place m unit disks, for a given constant m≥1, such that the total weight of the points from P inside the union of the disks is maximized. We present algorithms that compute, for any fixed ε > 0, a (1 - ε)-approximation to the optimal solution in O(nlog n) time.In the second problem we want to place a single disk with center in a given constant-complexity region X such that the total weight of the points from P inside the disk is minimized. Here we present an algorithm that computes, for any fixed ε > 0, in O(nlog 2n) expected time a disk that is, with high probability, a (1 + ε)- approximation to the optimal solution.

AB - Let P be a set of n weighted points. We study approximation algorithms for the following two continuous facility-location problems.In the first problem we want to place m unit disks, for a given constant m≥1, such that the total weight of the points from P inside the union of the disks is maximized. We present algorithms that compute, for any fixed ε > 0, a (1 - ε)-approximation to the optimal solution in O(nlog n) time.In the second problem we want to place a single disk with center in a given constant-complexity region X such that the total weight of the points from P inside the disk is minimized. Here we present an algorithm that computes, for any fixed ε > 0, in O(nlog 2n) expected time a disk that is, with high probability, a (1 + ε)- approximation to the optimal solution.

KW - Facility location

KW - Geometric optimization

KW - Random sample

KW - Weighted points

UR - http://www.scopus.com/inward/record.url?scp=70349732202&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70349732202&partnerID=8YFLogxK

U2 - 10.1007/s00224-008-9135-9

DO - 10.1007/s00224-008-9135-9

M3 - Article

AN - SCOPUS:70349732202

VL - 45

SP - 446

EP - 469

JO - Theory of Computing Systems

JF - Theory of Computing Systems

SN - 1432-4350

IS - 3

ER -