Line Transversals in Large T(3)- and T(4)-Families of Congruent Discs

Autor:	Aladár Heppes
Rok vydání:	2008
Předmět:	Combinatorics Reduction (recursion theory) Transversal (geometry) Computational Theory and Mathematics Common line Line (geometry) Discrete Mathematics and Combinatorics Geometry and Topology Upper and lower bounds Unit (ring theory) Theoretical Computer Science Mathematics
Zdroj:	Discrete & Computational Geometry. 40:312-318
ISSN:	1432-0444 0179-5376
DOI:	10.1007/s00454-008-9071-0
Popis:	A family of closed discs is said to have property T(k) if to every subset of at most k discs there belongs a common line transversal. A family of discs is said to be d-disjoint, d≥1, if the mutual distance between the centers of the discs is larger than d. It is known that a d-disjoint T(3)-family ℱ of unit diameter discs has a line transversal if $d=\sqrt{2}$. Similarly, a d-disjoint T(4)-family has a line transversal if $d=2/\sqrt{3}$. Both results are sharp in d, i.e., they do not hold for smaller values of d. The main result of this paper is that while the above lower bounds on d cannot be relaxed in general, some reduction of d can be compensated by imposing a proper d-dependent lower bound on the size of the family in both cases.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::039a64c7502f84d5824320197d6a8229 https://doi.org/10.1007/s00454-008-9071-0 Zobrazit plný text záznamu Full text from SpringerLink