Lines Pinning Lines

Boris Aronov; Otfried Cheong; Xavier Goaoc; Günter Rote

doi:10.1007/s00454-010-9288-6

Lines Pinning Lines

Boris Aronov, Otfried Cheong, Xavier Goaoc, Günter Rote

Research output: Contribution to journal › Article › peer-review

Abstract

A line ℓ is a transversal to a family F of convex polytopes in ℝ³ if it intersects every member of F. If, in addition, ℓ is an isolated point of the space of line transversals to F, we say that F is a pinning of ℓ. We show that any minimal pinning of a line by polytopes in ℝ³ such that no face of a polytope is coplanar with the line has size at most eight. If in addition the polytopes are pairwise disjoint, then it has size at most six.

Original language	English (US)
Pages (from-to)	230-260
Number of pages	31
Journal	Discrete and Computational Geometry
Volume	45
Issue number	2
DOIs	https://doi.org/10.1007/s00454-010-9288-6
State	Published - Mar 2011

Keywords

Geometric transversal
Helly-type theorem
Line geometry

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1007/s00454-010-9288-6

Cite this

@article{671a8eee294f4a65b905a31e080853d9,

title = "Lines Pinning Lines",

abstract = "A line ℓ is a transversal to a family F of convex polytopes in ℝ3 if it intersects every member of F. If, in addition, ℓ is an isolated point of the space of line transversals to F, we say that F is a pinning of ℓ. We show that any minimal pinning of a line by polytopes in ℝ3 such that no face of a polytope is coplanar with the line has size at most eight. If in addition the polytopes are pairwise disjoint, then it has size at most six.",

keywords = "Geometric transversal, Helly-type theorem, Line geometry",

author = "Boris Aronov and Otfried Cheong and Xavier Goaoc and G{\"u}nter Rote",

note = "Funding Information: B.A. was partially supported by a grant from the US–Israel Binational Science Foundation, by NSA MSP Grant H98230-06-1-0016, and by NSF Grant CCF-08-30691. Part of the work of B.A. on this paper was carried out while visiting KAIST in the summer of 2008, supported by the Brain Korea 21 Project, the School of Information Technology, KAIST, in 2008. The cooperation by O.C. and X.G. was supported by the INRIA {\'E}quipe Associ{\'e}e KI. O.C. was supported by the Mid-career Researcher Program through NRF grant funded by the MEST (No. R01-2008-000-11607-0).",

year = "2011",

month = mar,

doi = "10.1007/s00454-010-9288-6",

language = "English (US)",

volume = "45",

pages = "230--260",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "2",

}

TY - JOUR

T1 - Lines Pinning Lines

AU - Aronov, Boris

AU - Cheong, Otfried

AU - Goaoc, Xavier

AU - Rote, Günter

N1 - Funding Information: B.A. was partially supported by a grant from the US–Israel Binational Science Foundation, by NSA MSP Grant H98230-06-1-0016, and by NSF Grant CCF-08-30691. Part of the work of B.A. on this paper was carried out while visiting KAIST in the summer of 2008, supported by the Brain Korea 21 Project, the School of Information Technology, KAIST, in 2008. The cooperation by O.C. and X.G. was supported by the INRIA Équipe Associée KI. O.C. was supported by the Mid-career Researcher Program through NRF grant funded by the MEST (No. R01-2008-000-11607-0).

PY - 2011/3

Y1 - 2011/3

N2 - A line ℓ is a transversal to a family F of convex polytopes in ℝ3 if it intersects every member of F. If, in addition, ℓ is an isolated point of the space of line transversals to F, we say that F is a pinning of ℓ. We show that any minimal pinning of a line by polytopes in ℝ3 such that no face of a polytope is coplanar with the line has size at most eight. If in addition the polytopes are pairwise disjoint, then it has size at most six.

AB - A line ℓ is a transversal to a family F of convex polytopes in ℝ3 if it intersects every member of F. If, in addition, ℓ is an isolated point of the space of line transversals to F, we say that F is a pinning of ℓ. We show that any minimal pinning of a line by polytopes in ℝ3 such that no face of a polytope is coplanar with the line has size at most eight. If in addition the polytopes are pairwise disjoint, then it has size at most six.

KW - Geometric transversal

KW - Helly-type theorem

KW - Line geometry

UR - http://www.scopus.com/inward/record.url?scp=79251599287&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79251599287&partnerID=8YFLogxK

U2 - 10.1007/s00454-010-9288-6

DO - 10.1007/s00454-010-9288-6

M3 - Article

AN - SCOPUS:79251599287

SN - 0179-5376

VL - 45

SP - 230

EP - 260

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 2

ER -

Lines Pinning Lines

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this