Covering many or few points with unit disks

Mark De Berg, Sergio Cabello, Sariel Har-Peled

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 - ε)-approximation to the optimal solution in O(n log n + ε-4m log2m(1/ε)) 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 ε > 0, with high probability a (1 + ε)-approximation to the optimal solution in O(n(log 3 n + ε-4 log2 n)) expected time.

Original languageEnglish (US)
Title of host publicationApproximation and Online Algorithms - 4th International Workshop, WAOA 2006, Revised Papers
PublisherSpringer
Pages55-68
Number of pages14
ISBN (Print)9783540695134
DOIs
StatePublished - 2007
Event4th Workshop on Approximation and Online Algorithms, WAOA 2006 - Zurich, Switzerland
Duration: Sep 14 2006Sep 15 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4368 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other4th Workshop on Approximation and Online Algorithms, WAOA 2006
Country/TerritorySwitzerland
CityZurich
Period9/14/069/15/06

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

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

Cite this