Maths Olympiad Prep

Library / /21 of 70

Geometry Difficulty 8.1 Shortlist Prove it Romania

Given a set L\mathcal{L} of lines in general position in the plane (no two lines in L\mathcal{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 6L6|\mathcal{L}|.
Chazelle et al., Edelsbrunner et al.

Solution

Assume without loss of generality that \ell is horizontal and does not pass through any vertex of the arrangement of lines in L\mathcal{L}.

First, we shall bound the total number of edges of the upper parts of all faces intersected by \ell, that is, those parts that lie above \ell. The boundary of the upper part of such a face KK consists of two convex chains of edges, the left and right chain, and a portion of \ell. If the upper part of KK is bounded, then the left and right chains meet at the topmost vertex of KK. Otherwise, the last (topmost) edges of these chains are half-lines. The edges belonging to the left (respectively, right) chain, with the exception of the topmost edge, are called the left (respectively, right) edges of KK.
We claim that every line in L\mathcal{L} contains at most one left edge. Suppose, if possible, that some line in L\mathcal{L} has two portions ee and ee' that are left edges of KK and KK', respectively, where ee' is above ee. Then the line supporting the topmost edge of the left chain of KK would cross KK', contradicting the fact that KK' is a face of the arrangement of lines in L\mathcal{L}. Hence, the total number of left (respectively, right) edges of the upper parts of the faces intersected by \ell is at most L|\mathcal{L}|. Taking into account the topmost edges of the chains, the total number of edges of the upper parts of the faces intersected by \ell is at most 4L4|\mathcal{L}|. The same argument applies verbatim for the lower parts of these faces. Consequently, the total number of edges of the faces intersected by \ell is at most 8L2L=6L8|\mathcal{L}| - 2|\mathcal{L}| = 6|\mathcal{L}|; the second term is due to the fact that the edges crossed by \ell are counted twice: once in the upper parts and once in the lower parts.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.