Lauen, Sören
Geometric Set Cover and Hitting Sets for Polytopes in R³
Abstract
Suppose we are given a finite set of points $P$ in $R^3$ and a
collection of polytopes $mathcal{T}$ that are all translates of
the same polytope $T$. We consider two problems in this paper.
The first is the set cover problem where we want to select a
minimal number of polytopes from the collection $mathcal{T}$ such
that their union covers all input points $P$. The second problem
that we consider is finding a hitting set for the set of polytopes
$mathcal{T}$, that is, we want to select a minimal number of
points from the input points $P$ such that every given polytope is
hit by at least one point.
We give the first constantfactor approximation algorithms for both
problems. We achieve this by providing an epsilonnet for
translates of a polytope in $R^3$ of size
$\bigO(frac{1{epsilon)$.
BibTeX  Entry
@InProceedings{lauen:LIPIcs:2008:1367,
author = {S{\"o}ren Lauen},
title = {{Geometric Set Cover and Hitting Sets for Polytopes in {$R^3$}}},
booktitle = {25th International Symposium on Theoretical Aspects of Computer Science},
pages = {479490},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897064},
ISSN = {18688969},
year = {2008},
volume = {1},
editor = {Susanne Albers and Pascal Weil},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2008/1367},
URN = {urn:nbn:de:0030drops13675},
doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2008.1367},
annote = {Keywords: Computational Geometry, EpsilonNets, Set Cover, Hitting Sets}
}
2008
Keywords: 

Computational Geometry, EpsilonNets, Set Cover, Hitting Sets 
Seminar: 

25th International Symposium on Theoretical Aspects of Computer Science

Related Scholarly Article: 


Issue date: 

2008 
Date of publication: 

2008 