6
$\begingroup$

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?

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

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)$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.