Given a set $L$ of lines in general position in the plane (no two lines in $L$ are parallel, and no three lines are concurrent) and another line $\ell$, show that the total number of edges of all faces in the corresponding arrangement, intersected by $\ell$, is at most $6|L|$. Chazelle et al., Edelsbrunner et al.
Problem
Source: BMO&IMO TST
Tags: geometry, combinatorics unsolved, combinatorics, Probabilistic Method
27.09.2016 06:20
Can anybody post a solution?
27.09.2016 21:56
Any idea $?$
17.09.2017 14:46
Anyone has a solution?Thanks!!!
11.09.2018 02:56
http://www2.math.technion.ac.il/~room/ps_files/zonespl.pdf
30.09.2021 19:20
P.S. I can't access the file in the above post. It would mean a lot if someone could share a new link or attach a pdf (if that's allowed).
15.05.2022 11:01
Since the file uploaded by the @juckter is not accessible, I'll put it's new link. It's Rom Pinchasi's paper <The Zone Theorem Revisited> written in 2011. You can find it's google drive file in his homepage. <The Zone Theorem Revisited> In this paper, Rom proved that in the set of $n+1$ lines on the plane and line $L$ in this set, the total number of edges of all faces that having $L$ as one it's edge is less or equal to $9.5n-3$, and this bound is tight. This proof is based on the result in the paper <The Power of Geometric Duality>, written by B. Chazelle, L. J. Guibas, D. T. Lee in 1985. It proved that this total number is bounded by $10n-2$ by using the same idea @phoenixfire used in #6. So you can solve our Romanian TST problem by using the idea in the paper below; <The Power of Geometric Duality> This problem is also appeared in 2021 239MO problem 7.
15.05.2022 11:38
Thank you @above.