Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
The Maximum Number of Tangencies Among Convex Regions with a Triangle-Free Intersection Graph
verfasst von : Eyal Ackerman
Erschienen in: Thirty Essays on Geometric Graph Theory
Verlag: Springer New York
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Let \(t(\mathcal{C})\) be the number of tangent pairs among a set \(\mathcal{C}\) of n Jordan regions in the plane. Pach et al. [Tangencies between families of disjoint regions in the plane, in Proceedings of the 26th ACM Symposium on Computational Geometry (SoCG 2010), Snowbird, June 2010, pp. 423–428] showed that if \(\mathcal{C}\) consists of convex bodies and its intersection graph is bipartite, then \(t(\mathcal{C}) \leq 4n - \Theta (1)\), and, moreover, there are such sets that admit at least \(3n - \Theta (\sqrt{n})\) tangencies. We close this gap and generalize their result by proving that the correct bound is \(3n - \Theta (1)\), even when the intersection graph of \(\mathcal{C}\) is only assumed to be triangle-free.