The Maximum Number of Tangencies Among Convex Regions with a Triangle-Free Intersection Graph

Eyal Ackerman ()
Additional contact information
Eyal Ackerman: University of Haifa at Oranim, Department of Mathematics, Physics, and Computer Science

A chapter in Thirty Essays on Geometric Graph Theory, 2013, pp 19-30 from Springer

Abstract: 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.

Keywords: Intersection Graph; Tangent Pairs; Jordan Region; Convex Bodies; Correct Boundary (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4614-0110-0_3

Ordering information: This item can be ordered from
http://www.springer.com/9781461401100

DOI: 10.1007/978-1-4614-0110-0_3

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().