HAL - INRIA :: [inria-00179277, version 3] Helly-type theorems for approximate covering

inria-00179277, version 3

Helly-type theorems for approximate covering

Julien Demouth () ¹, Olivier Devillers () ², Marc Glisse () ¹, Xavier Goaoc () ¹

N° RR-6342 (2007)

Résumé : Let F be a covering of a unit ball U in Rd by unit balls. We prove that for any epsilon >0, the smallest subset of F leaving at most a volume epsilon of U uncovered has size O(epsilon^((1-d)/2)polylog 1/epsilon). We give an example showing that this bound is tight in the worst-case, up to a logarithmic factor, and deduce an algorithm to compute such a small subset of F. We then extend these results in several directions, including covering boxes by boxes and visibility among disjoint unit balls in R3.

1 : VEGAS (INRIA Lorraine - LORIA)
INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine
2 : GEOMETRICA (INRIA Sophia Antipolis / INRIA Futurs)
INRIA

inria-00179277, version 3
http://hal.inria.fr/inria-00179277
oai:hal.inria.fr:inria-00179277
Contributeur : Olivier Devillers <>
Soumis le : Lundi 5 Novembre 2007, 13:20:25
Dernière modification le : Jeudi 16 Octobre 2008, 14:55:33

Voir la fiche détaillée

Documents associés

PDF :

Exporter

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="report"><head>Rapports</head>
<biblStruct type="report" xml:id="inria-00179277"><monogr>
<author><persName><forename>Julien</forename><surname>Demouth</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">VEGAS</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine</orgName>
</affiliation>
</author>
<author><persName><forename>Olivier</forename><surname>Devillers</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Sophia Antipolis / INRIA Futurs</orgName>
<orgName type="team">GEOMETRICA</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
</affiliation>
</author>
<author><persName><forename>Marc</forename><surname>Glisse</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">VEGAS</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine</orgName>
</affiliation>
</author>
<author><persName><forename>Xavier</forename><surname>Goaoc</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">VEGAS</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine</orgName>
</affiliation>
</author>
<title type="main" level="m">Helly-type theorems for approximate covering</title><title type="main" level="m">Helly-type theorems for approximate covering</title><imprint><biblScope type="publicationDate">2007-00-00</biblScope><biblScope type="pp">12</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00179277</idno><idno type="HALFile">http://hal.inria.fr/inria-00179277/PDF/RR.pdf</idno></biblStruct>
</listBibl>
</listBibl>