patternMinor
Number of vertices and edges lies on the boundary of bounded cells in line arrangement
Viewed 0 times
numberedgesthelineliesarrangementcellsboundaryandbounded
Problem
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?
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?
Solution
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)$.
Context
StackExchange Computer Science Q#132175, answer score: 3
Revisions (0)
No revisions yet.