Given a set of lines in general position in the plane (no two lines in 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 .
Chazelle et al., Edelsbrunner et al.
Solution
Assume without loss of generality that is horizontal and does not pass through any vertex of the arrangement of lines in .
First, we shall bound the total number of edges of the upper parts of all faces intersected by , that is, those parts that lie above . The boundary of the upper part of such a face consists of two convex chains of edges, the left and right chain, and a portion of . If the upper part of is bounded, then the left and right chains meet at the topmost vertex of . 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 .
We claim that every line in contains at most one left edge. Suppose, if possible, that some line in has two portions and that are left edges of and , respectively, where is above . Then the line supporting the topmost edge of the left chain of would cross , contradicting the fact that is a face of the arrangement of lines in . Hence, the total number of left (respectively, right) edges of the upper parts of the faces intersected by is at most . Taking into account the topmost edges of the chains, the total number of edges of the upper parts of the faces intersected by is at most . The same argument applies verbatim for the lower parts of these faces. Consequently, the total number of edges of the faces intersected by is at most ; the second term is due to the fact that the edges crossed by are counted twice: once in the upper parts and once in the lower parts.