Minimum-cost coverage of point sets by disks
or How to spread rumors without wearing out your voice or your shoes

Written with Helmut Alt, Esther M. Arkin, Hervé Brönnimann, Sándor P. Fekete, Christian Knauer, Jonathan Lenchner*, Joseph S. B. Mitchell, and Kim Whittlesey.

Proceedings of the 22nd Annual ACM Symposium on Computational Geometry, 449-458, 2006.


We consider a class of geometric facility location problems in which the goal is to determine a set X of disks given by their centers and radii that cover a given set of demand points in the plane at the smallest possible cost. We consider cost functions of the form ∑j rjα where rα is the cost of transmission to radius r. Special cases arise for α=1 and α=2; power consumption models in wireless network design often use an exponent α>2. Different scenarios arise according to possible restrictions on the transmission centers, which may be constrained to lie in a given discrete set, to lie on a line, etc.

We obtain several new results, including (a) exact and approximation algorithms for selecting transmission points on a given line in order to cover the demand points; (b) approximation algorithms (and an algebraic intractability result) for selecting an optimal line on which to place transmission points to cover the demand points; and (c) a polynomial-time approximation scheme for the problem of computing a minimum cost covering tour, in which the total cost is a linear combination of the transmission cost for the set of disks and the length of a path that connects the centers of the disks.

Publications - Jeff Erickson ( 21 Jan 2012