HAL - INRIA :: [inria-00395837, version 1] Lower Bounds for Pinning Lines by Balls

inria-00395837, version 1

Lower Bounds for Pinning Lines by Balls

Otfried Cheong ¹, Xavier Goaoc () ², Andreas Holmsen ¹

N° RR-6961 (2009)

Résumé : A line L is a transversal to a family F of convex objects in R^d if it intersects every member of F. In this paper we show that for every integer d>2 there exists a family of 2d-1 pairwise disjoint unit balls in R^d with the property that every subfamily of size 2d-2 admits a transversal, yet any line misses at least one member of the family. This answers a question of Danzer from 1957.

1 : Department of Electrical Engineering [Korea Advanced Institute of Science and Technology] (KAIST)
Korea Advanced Institute of Science and Technology
2 : VEGAS (INRIA Lorraine - LORIA)
INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine

inria-00395837, version 1
http://hal.inria.fr/inria-00395837
oai:hal.inria.fr:inria-00395837
Contributeur : Xavier Goaoc <>
Soumis le : Mardi 16 Juin 2009, 14:52:33
Dernière modification le : Mercredi 17 Juin 2009, 11:08:32

Voir la fiche détaillée

Documents associés

PDF :

PS :

arXiv : 0906.2924

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-00395837"><monogr>
<author><persName><forename>Otfried</forename><surname>Cheong</surname></persName>
<affiliation>
<orgName type="laboratory">KAIST</orgName>
<orgName type="team">Department of Electrical Engineering [Korea Advanced Institute of Science and Technology]</orgName>
<country>KR</country>
<orgName type="institution">Korea Advanced Institute of Science and Technology</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>
<author><persName><forename>Andreas</forename><surname>Holmsen</surname></persName>
<affiliation>
<orgName type="laboratory">KAIST</orgName>
<orgName type="team">Department of Electrical Engineering [Korea Advanced Institute of Science and Technology]</orgName>
<country>KR</country>
<orgName type="institution">Korea Advanced Institute of Science and Technology</orgName>
</affiliation>
</author>
<title type="main" level="m">Lower Bounds for Pinning Lines by Balls</title><title type="main" level="m">Lower Bounds for Pinning Lines by Balls</title><imprint><biblScope type="publicationDate">2009-00-00</biblScope><biblScope type="pp">12</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00395837</idno><idno type="HALFile">http://hal.inria.fr/inria-00395837/PDF/RR-6961.pdf</idno></biblStruct>
</listBibl>
</listBibl>