# Geometric Dominating Set and Set Cover via Local Search

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 May 2016.

## 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)

In this paper, we study two classic optimization problems: minimum geometric dominating set and set cover. In the dominating-set problem, for a given set of objects in the plane as input, the objective is to choose a minimum number of input objects such that every input object is dominated by the chosen set of objects. Here, one object is dominated by another if both of them have a nonempty intersection region. For the second problem, for a given set of points and objects in a plane, the objective is to choose a minimum number of objects to cover all the points. This is a special version of the set-cover problem. For both problems obtaining a PTAS remains open for a large class of objects. For the dominating-set problem, we prove that a popular local-search algorithm leads to an (1+varepsilon) approximation for object sets consisting of homothetic set of convex objects (which includes arbitrary squares, k-regular polygons, translated and scaled copies of a convex set, etc.) in nO(1/varepsilon2) time. On the other hand, the same technique leads to a PTAS for geometric covering problem when the objects are convex pseudodisks (which includes disks, unit height rectangles, homothetic convex objects, etc.). As a consequence, we obtain an easy to implement approximation algorithm for both problems for a large class of objects, significantly improving the best known approximation guarantees.