Back to Search
Start Over
Beyond the Richter-Thomassen Conjecture
- Source :
- Scopus-Elsevier
- Publication Year :
- 2015
- Publisher :
- Society for Industrial and Applied Mathematics, 2015.
-
Abstract
- If two closed Jordan curves in the plane have precisely one point in common, then it is called a {\em touching point}. All other intersection points are called {\em crossing points}. The main result of this paper is a Crossing Lemma for closed curves: In any family of $n$ pairwise intersecting simple closed curves in the plane, no three of which pass through the same point, the number of crossing points exceeds the number of touching points by a factor of at least $\Omega((\log\log n)^{1/8})$. As a corollary, we prove the following long-standing conjecture of Richter and Thomassen: The total number of intersection points between any $n$ pairwise intersecting simple closed curves in the plane, no three of which pass through the same point, is at least $(1-o(1))n^2$.
- Subjects :
- Computational Geometry (cs.CG)
FOS: Computer and information sciences
F.2.2
G.2.1
010102 general mathematics
0102 computer and information sciences
16. Peace & justice
01 natural sciences
010201 computation theory & mathematics
FOS: Mathematics
Mathematics - Combinatorics
Computer Science - Computational Geometry
Combinatorics (math.CO)
0101 mathematics
05C10, 05C35, 05D99, 52C30, 52C45, 52C10
Subjects
Details
- Database :
- OpenAIRE
- Journal :
- Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms
- Accession number :
- edsair.doi.dedup.....cf9855ff9277b16863928b4f9217b955