HAL - INRIA :: [inria-00404171, version 1] Helly-type theorems for approximate covering

inria-00404171, version 1

%% inria-00404171, version 1
%% http://hal.inria.fr/inria-00404171/en/
@article{DEMOUTH:2009:INRIA-00404171:1,
	title = { {H}elly-type theorems for approximate covering},
	author = {{D}emouth, {J}ulien and {D}evillers, {O}livier and {G}lisse, {M}arc and {G}oaoc, {X}avier},
	abstract = {{L}et {F} ∪ {{U} } be a collection of convex sets in {R}d such that {F} covers {U} . {W}e prove that if the elements of {F} and {U} have comparable size then a small subset of {F} suffices to cover most of the volume of {U} ; we analyze how small this subset can be depending on the geometry of the elements of {F} , and show that smooth convex sets and axis parallel squares behave differently. {W}e obtain similar results for surface-to-surface visibility amongst balls in 3 dimensions for a notion of volume related to form factor. {F}or each of these situations, we give an algorithm that takes {F} and {U} as input and computes in time {O} (|{F} | ∗ |{H}ϵ |) either a point in {U} not covered by or a subset ϵ covering {U} up to a measure ϵ, with ϵ meeting our combinatorial bounds.},
	language = {{A}nglais},
	affiliation = {{VEGAS} - {INRIA} {L}orraine - {LORIA} - {INRIA} - {CNRS} : {UMR}7503 - {U}niversit{\'e} {H}enri {P}oincar{\'e} - {N}ancy {I} - {U}niversit{\'e} {N}ancy {II} - {I}nstitut {N}ational {P}olytechnique de {L}orraine - {GEOMETRICA} - {INRIA} {S}ophia {A}ntipolis / {INRIA} {S}aclay - {I}le de {F}rance - {INRIA} - {G}renoble {I}mages {P}arole {S}ignal {A}utomatique - {GIPSA}-lab - {CNRS} : {UMR}5216 - {U}niversit{\'e} {J}oseph {F}ourier - {G}renoble {I} - {U}niversit{\'e} {P}ierre {M}end{\`e}s-{F}rance - {G}renoble {II} - {U}niversit{\'e} {S}tendhal - {G}renoble {III} - {I}nstitut {P}olytechnique de {G}renoble },
	publisher = {{S}pringer },
	pages = {379--398 },
	journal = {{D}iscrete \& {C}omputational {G}eometry },
	volume = {42 },
	audience = {internationale },
	doi = {10.1007/s00454-009-9167-1 },
    year = {2009},
    URL = {http://dx.doi.org/10.1007/s00454-009-9167-1 http://hal.inria.fr/inria-00404171/en/},
    URL = {http://hal.inria.fr/inria-00404171/PDF/appcover.pdf},
}

<?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="article"><head>Articles dans des revues avec comité de lecture</head>
<biblStruct type="article" xml:id="inria-00404171"><analytic>
<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 Saclay - Ile de France</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">GIPSA-lab</orgName>
<orgName type="team">Grenoble Images Parole Signal Automatique</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR5216</orgName>
<orgName type="institution">Université Joseph Fourier - Grenoble I</orgName>
<orgName type="institution">Université Pierre Mendès-France - Grenoble II</orgName>
<orgName type="institution">Université Stendhal - Grenoble III</orgName>
<orgName type="institution">Institut Polytechnique de Grenoble</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="a">Helly-type theorems for approximate covering</title></analytic><monogr><title level="j" type="main">Discrete & Computational Geometry</title><imprint><publisher>Springer</publisher><biblScope type="publicationDate">2009</biblScope><biblScope type="vol">42</biblScope><biblScope type="issue">3</biblScope><biblScope type="pp">379--398</biblScope></imprint></monogr><idno type="doi">10.1007/s00454-009-9167-1</idno><idno type="HALid">http://hal.inria.fr/inria-00404171/en/</idno><idno type="HALFile">http://hal.inria.fr/inria-00404171/PDF/appcover.pdf</idno></biblStruct>
</listBibl>
</listBibl>

Helly-type theorems for approximate covering

Julien Demouth (

) ¹, Olivier Devillers (

http://www-sop.inria.fr/geometrica/team/Olivier.Devillers/

) ², Marc Glisse (

) ³, Xavier Goaoc (

) ¹

(2009)

Accès au texte intégral
PDF

Discrete & Computational Geometry 42, 3 (2009) 379--398

Lien vers texte intégral chez l'éditeur

Résumé : Let F ∪ {U } be a collection of convex sets in Rd such that F covers U . We prove that if the elements of F and U have comparable size then a small subset of F suffices to cover most of the volume of U ; we analyze how small this subset can be depending on the geometry of the elements of F , and show that smooth convex sets and axis parallel squares behave differently. We obtain similar results for surface-to-surface visibility amongst balls in 3 dimensions for a notion of volume related to form factor. For each of these situations, we give an algorithm that takes F and U as input and computes in time O (|F | ∗ |Hϵ |) either a point in U not covered by or a subset ϵ covering U up to a measure ϵ, with ϵ meeting our combinatorial bounds.

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 Saclay - Ile de France)
	INRIA
3 :	Grenoble Images Parole Signal Automatique (GIPSA-lab)
	CNRS : UMR5216 – Université Joseph Fourier - Grenoble I – Université Pierre Mendès-France - Grenoble II – Université Stendhal - Grenoble III – Institut Polytechnique de Grenoble

Domaine

Informatique/Géométrie algorithmique

DOI : 10.1007/s00454-009-9167-1


inria-00404171, version 1
http://hal.inria.fr/inria-00404171/fr/
oai:hal.inria.fr:inria-00404171_v1
Contributeur : Olivier Devillers <>
Soumis le : Mercredi 15 Juillet 2009, 15:58:31
Dernière modification le : Jeudi 12 Novembre 2009, 11:42:35