On Piercing Sets of ObjectsReportar como inadecuado




On Piercing Sets of Objects - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

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$.

Keywords : COMPUTATIONAL GEOMETRY





Autor: Matthew J. Katz - Franck Nielsen

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados