# Faster Approximation Algorithms for Geometric Set Cover

arXiv: https://arxiv.org/abs/2003.13420 · HTML: https://mlsanity.com/paper/2003.13420/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Mar 2020.

## Built on by (most cited first, 1 of 1)

- [Constraint Model for the Satellite Image Mosaic Selection Problem](https://mlsanity.com/paper/2312.04210/) (2023)

## Abstract (arXiv)

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(nlog4 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(nlog3 nloglog n)-time algorithm. With further new ideas, we obtain a still faster randomized O(nlog n(loglog n)O(1))-time algorithm. For the weighted problem, we also give a randomized O(nlog4nloglog n)-time, O(1)-approximation algorithm, by simple modifications to the MWU method and the quasi-uniform sampling technique.