Skip to Main content Skip to Navigation
Reports

On Piercing Sets of Objects

Matthew J. Katz 1 Franck Nielsen
1 PRISME - Geometry, Algorithms and Robotics
CRISAM - Inria Sophia Antipolis - Méditerranée
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 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$.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00073817
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 1:49:33 PM
Last modification on : Saturday, January 27, 2018 - 1:31:31 AM
Long-term archiving on: : Sunday, April 4, 2010 - 9:31:12 PM

Identifiers

  • HAL Id : inria-00073817, version 1

Collections

Citation

Matthew J. Katz, Franck Nielsen. On Piercing Sets of Objects. RR-2874, INRIA. 1996. ⟨inria-00073817⟩

Share

Metrics

Record views

156

Files downloads

216