On the transversal Helly numbers of disjoint and overlapping disks (Q2502309)

From MaRDI portal
Revision as of 09:50, 5 August 2023 by Importer (talk | contribs) (‎Created a new Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
On the transversal Helly numbers of disjoint and overlapping disks
scientific article

    Statements

    On the transversal Helly numbers of disjoint and overlapping disks (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    12 September 2006
    0 references
    Let \(\mathcal F\) denote a family of unit diameter discs in the plane. Let \(T(k)\) be the property that any subfamily \(\mathcal F'\subseteq \mathcal F\) of \(k\) discs has a line transversal, i.e., a line intersecting each disc in \(\mathcal F'\). Call \(\mathcal F\) \(t\)-disjoint if the distance between each pair of centres is greater than \(t>0\). For each \(k\geq 3\), let \(t_k\) be the infimum of the \(t>0\) such that any \(t\)-disjoint \(\mathcal F\) with property \(T(k)\) has a line transversal. The paper shows that \(t_3=\sqrt{2}\), \(t_4=2\sqrt{3}\), and \(t_k\leq c/(k-3)\) for all \(k\geq 5\), where \(c\approx 6.2508\). In particular, for each \(t>0\), a \(t\)-disjoint family \(\mathcal F\) has a finite transversal Helly number. It is also shown that asymptotically \(t_k\gtrsim \pi/k\) as \(k\to\infty\), which gives \(t_k=\Theta(1/k)\). Reviewer's remark: The survey on geometric transversals cited in the paper is by \textit{R.~Wenger} [Chapter 4 of Handbook of Discrete and Computational Geometry, J.E.~Goodman, J.~O'Rourke, eds., CRC Press. 63--82 (1997; Zbl 0912.52006)].
    0 references
    line transversals
    0 references
    geometric transversal theory
    0 references
    Helly numbers
    0 references

    Identifiers