10.4230/LIPICS.STACS.2008.1367
Lauen, Sören
Sören
Lauen
Geometric Set Cover and Hitting Sets for Polytopes in R³
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2008
Computational Geometry
Epsilon-Nets
Set Cover
Hitting Sets
Albers, Susanne
Susanne
Albers
Weil, Pascal
Pascal
Weil
2008
2008-02-06
2008-02-06
2008-02-06
en
urn:nbn:de:0030-drops-13675
10.4230/LIPIcs.STACS.2008
978-3-939897-06-4
1868-8969
10.4230/LIPIcs.STACS.2008
LIPIcs, Volume 1, STACS 2008
25th International Symposium on Theoretical Aspects of Computer Science
2013
1
42
479
490
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Albers, Susanne
Susanne
Albers
Weil, Pascal
Pascal
Weil
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2008
1
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
180701 bytes
application/pdf
Creative Commons Attribution-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
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 constant-factor approximation algorithms for both
problems. We achieve this by providing an epsilon-net for
translates of a polytope in $R^3$ of size
$\bigO(frac{1{epsilon)$.
LIPIcs, Vol. 1, 25th International Symposium on Theoretical Aspects of Computer Science, pages 479-490