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 ℓ, show that the total number of edges of all faces in the corresponding arrangement, intersected by ℓ, 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.