On Piercing Sets of Objects

Résumé du livre

Abstract: "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 poiints. Finding the smallest integer k such that a set is k- pierceable is NP-complete. In this paper, 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 congurent homothets of K."