Faster approximation algorithms for geometric set cover

Timothy M. Chan, Qizheng He

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


We improve the running times of O(1)-approximation algorithms for the set cover problem in geometric settings, specifically, covering points by disks in the plane, or covering points by halfspaces in three dimensions. In the unweighted case, Agarwal and Pan [SoCG 2014] gave a randomized O(n log4 n)-time, O(1)-approximation algorithm, by using variants of the multiplicative weight update (MWU) method combined with geometric data structures. We simplify the data structure requirement in one of their methods and obtain a deterministic O(n log3 n log log n)-time algorithm. With further new ideas, we obtain a still faster randomized O(n log n(log log n)O(1))-time algorithm. For the weighted problem, we also give a randomized O(n log4 n log log n)-time, O(1)-approximation algorithm, by simple modifications to the MWU method and the quasi-uniform sampling technique.

Original languageEnglish (US)
Title of host publication36th International Symposium on Computational Geometry, SoCG 2020
EditorsSergio Cabello, Danny Z. Chen
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771436
StatePublished - Jun 1 2020
Event36th International Symposium on Computational Geometry, SoCG 2020 - Zurich, Switzerland
Duration: Jun 23 2020Jun 26 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference36th International Symposium on Computational Geometry, SoCG 2020


  • Approximation algorithms
  • Multiplicate weight update method
  • Random sampling
  • Set cover
  • Shallow cuttings

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Faster approximation algorithms for geometric set cover'. Together they form a unique fingerprint.

Cite this