8481 articles  [english version]

inria-00073817, version 1

On Piercing Sets of Objects

Matthew J. Katz 1, Franck Nielsen

N° RR-2874 (1996)

Résumé : A set of objects is $k$-pierceable if there exists a set of $k$ points such that each object is pierced by (contains) at least one of these points. Finding the smallest integer $k$ such that a set is $k$-pierceable is NP-complete. In this technical report, we present efficient algorithms for finding a piercing set (i.e., a set of $k$ points as above) for several classes of convex objects and small values of $k$. In some of the cases, our algorithms imply known as well as new Helly-type theorems, thus adding to previous results of Danzer and Grünbaum who studied the case of axis-parallel boxes. The problems studied here are related to the collection of optimization problems in which one seeks the smallest scaling factor of a centrally symmetric convex object $K$, so that a set of points can be covered by $k$ congruent homothets of $K$.

  • 1 :  PRISME (INRIA Sophia Antipolis)
  • INRIA
  • Domaine : Informatique/Autre
  • Mots-clés : COMPUTATIONAL GEOMETRY
  • Référence interne : RR-2874
 
  • inria-00073817, version 1
  • oai:hal.inria.fr:inria-00073817
  • Contributeur : 
  • Soumis le : Mercredi 24 Mai 2006, 13:49:33
  • Dernière modification le : Mercredi 31 Mai 2006, 14:24:28