Number of vertices and edges lies on the boundary of bounded cells in line arrangement

I am learning computational geometry by myself using these lecture notes from ETH Zurich. Here is an exercise (8.9) I have been stuck for a few days:

For a line arrangement $$A$$ of a set of $$n$$ lines in $$R^2$$, let $$F$$ denote the union of the closure of all bounded cells. Show that the complexity (number of vertices and edges of the arrangement lying on the boundary) of $$F$$ is $$O(n)$$.

My intuition is to use induction, proving that when a new line $$l$$ is added, the number of added edges is a constant. This is similar to how we proved the zone theorem. However, I cannot figure it out. Can someone provide me with some hints?

• Observation: Although each cell is convex, the union of all cells is not necessarily. Example: imgur.com/ooiYWS6 – j_random_hacker Nov 12 '20 at 17:33

1 Answer

Consider 3 additional lines such that their arrangement consists of a single bounded (triangular) cell $$C$$ and $$F \subset C$$. Then every edge of $$F$$ belongs to a zone (using a terminology from your textbook) of at least one of the 3 added lines. And all 3 zones of 3 added lines contain at most $$30n$$ edges according to Zone Theorem. So $$F$$ has no more than $$30n$$ edges which is $$O(n)$$.

• Or use a bounding triangle for $\le 30n$ edges. – j_random_hacker Nov 12 '20 at 22:00
• @j_random_hacker Thank you, I've edited the answer. – Vladislav Bezhentsev Nov 12 '20 at 22:03