Covering many or few points with unit disks

M. Berg, de, S. Cabello, S. Har-Peled

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)
4 Downloads (Pure)

Abstract

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 a deterministic algorithm that can compute, for any e>0, a (1-e)-approximation to the optimal solution in O(n logn + e-4mlog2m (1/e)) 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 can compute, for any e>0, with high probability a (1+e)-approximation to the optimal solution in O(n (log3 n + e-4 log2 n )) expected time.
Original languageEnglish
Title of host publicationProceedings of the 4th International Workshop on Approximation and Online Algorithms (WAOA 2006) 14-15 September 2006, Zürich, Switzerland
EditorsT. Erlebach, C. Kaklamanis
Place of PublicationBerlin
PublisherSpringer
Pages55-68
ISBN (Print)978-3-540-69513-4
DOIs
Publication statusPublished - 2007
Eventconference; WAOA 2006, Zurich, Switzerland; 2006-09-14; 2006-09-15 -
Duration: 14 Sept 200615 Sept 2006

Publication series

NameLecture Notes in Computer Science
Volume4368
ISSN (Print)0302-9743

Conference

Conferenceconference; WAOA 2006, Zurich, Switzerland; 2006-09-14; 2006-09-15
Period14/09/0615/09/06
OtherWAOA 2006, Zurich, Switzerland

Fingerprint

Dive into the research topics of 'Covering many or few points with unit disks'. Together they form a unique fingerprint.

Cite this