when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-13675
URL:

### Geometric Set Cover and Hitting Sets for Polytopes in R³

 pdf-format:

### 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 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)\$.

### 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 =	{479--490},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-939897-06-4},
ISSN =	{1868-8969},
year =	{2008},
volume =	{1},
editor =	{Susanne Albers and Pascal Weil},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address =	{Dagstuhl, Germany},
URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1367},
URN =		{urn:nbn:de:0030-drops-13675},
doi =		{http://dx.doi.org/10.4230/LIPIcs.STACS.2008.1367},
annote =	{Keywords:  Computational Geometry, Epsilon-Nets, Set Cover, Hitting Sets}
}
```

 Keywords: Computational Geometry, Epsilon-Nets, Set Cover, Hitting Sets Seminar: 25th International Symposium on Theoretical Aspects of Computer Science Related Scholarly Article: Issue date: 2008 Date of publication: 2008

DROPS-Home | Fulltext Search | Imprint