REAL

Beyond the Richter-Thomassen conjecture

Pach, János and Rubin, Natan and Tardos, Gábor (2016) Beyond the Richter-Thomassen conjecture. In: 27th Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (3). Association for Computing Machinery, Red Hook NY, pp. 957-968. ISBN 978-1-5108-1967-2

[img]
Preview
Text
RichtertThomassenIIFOCS040215.pdf

Download (277kB) | Preview

Abstract

If two closed Jordan curves in the plane have precisely one point in common, then it is called a touching point-All other intersection points are called 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 fK(loglogn)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(l))n2.

Item Type: Book Section
Uncontrolled Keywords: Algorithms; Touching points; Same points; Jordan curves; Intersection points; Crossing point; Closed curve
Subjects: Q Science / természettudomány > QA Mathematics / matematika
SWORD Depositor: MTMT SWORD
Depositing User: MTMT SWORD
Date Deposited: 03 Jan 2017 14:41
Last Modified: 03 Jan 2017 14:41
URI: http://real.mtak.hu/id/eprint/44394

Actions (login required)

Edit Item Edit Item