This comes off an application of trapezoidal decomposition.
I am using a Binary Space Partition (BSP).
I am trying to prove this by induction.
Let’s say You are given a set of n non intersecting line segments in the plane, and you build a subdivision recursively as follows:
- the subdivision contains no segments and only one face, the entire space.
- (base case) When the first segment is inserted, this face is partitioned into two faces by a splitting line that contains this segment.
prove that the number of faces of a BSP subdivision is equal to n + 1 plus the total number of cuts?
Can I please get some help/hints on this proof?
Thanks
~JJ
You already argued the base case for $n=1$. Now we take a fixed $n$ and by hypothesis this creates $n+1$ faces. Then the induction step from $n \rightarrow n+1$ can be argued as follows.
We add a $n+1^\text{th}$ segment $s$. By definition $s$ only intersects the interior of exactly one face $f$ of the current $n+1$ faces. Then $s$ is connected to the boundary of $f$ on at least one point where the second endpoint is either at infinity or on the boundary of $f$ as well. Clearly $s$ is incident to exactly two faces, that is it split $f$ into two and creates exactly one additional face. Which establishes the correctness of the induction.