On piercing sets of objects
Matthew J. Katz, Frank Nielsen · 1996
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 paper, we present efficient algorithms for findinga piercing set (i.e., a set ofkpoints asabove) 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 Griinbaum who studied the case of axisparallel 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. h = h(C, P)associated with a class of objects C and a property P is