You can scroll down the question, if you're familiar with the construction of a 3d binary space partition as presented in the book Computational Geometry: Algorithms and Applications by Mark de Berg et al..
Let
- $S$ be a set of $n$ non-overlapping line segments in the plane
- $\ell(s)$ be the line which contains $s\in S$
- $\ell^+$ and $\ell^-$ be the half-plane above and below of a line $\ell$, respectively
Consider the following algorithm, called $\text{2dBSP}(S)$:
- Randomly shuffle the elements of $S$ such that each possible permutation of those elements has equal probability of appearance
- If $S$ contains at most one element, create a tree $T$ with value $S$
- Otherwise, pick the first element $s_1\in S$ and use $\ell:=\ell(s_1)$ to split the plane:
- Let $S^\pm:=\left\{s\cap l^\pm:s\in S\right\}$ and $T^\pm:=\text{2dBSP}(S^\pm)$
- Create a tree $T$ with left subtree $T^-$, right subtree $T^+$ and value $\left\{s\in S:s\subseteq\ell\right\}$
- Return $T$
Suppose we have chosen the first few splitting lines. These lines induce a subdivision of the plane whose regions correspond to nodes in the built tree. Consider one such region $r$. There can be segments $s$ in $S$ that cross $r$ completely (i.e. the fragment $f$ of $s$ contained in $f$ doesn't cut any segments inside $r$). Picking $f$ to split $r$ is called a free split.
Now, we want to use a set of $n$ non-intersecting triangles $t_1,\ldots, t_n$ in the space instead of $S$. Let $h_i$ be the plane which contains $t_i$. Since we cannot use the literal translation of $\text{2dBSP}$ if we want to be able to analyze the resulting algorithm, we use the following modification, called $\text{3dBSP}$:
- Randomly shuffle the elements of $S$ such that each possible permutation of those elements has equal probability of appearance
- for $i=1$ to $n$:
- Use $h_i$ to split every region where the split is "useful" and make all possible free splits
The definition of a free split can be translated literally to the 3d case.
You can find $\text{3dBSP}$ in the book above Lemma 12.3. A $2d$ example of its behavior, in contrast to $\text{2dBSP}$, is shown in the next image
where (a) is the result of $\text{2dBSP}$ and (b) is the result of a $2d$ variant of $\text{3dBSP}$.
Question: Let $k\in\left\{1,\ldots,n\right\}$ and $N$ be the number of fragments into which $t_k$ is cut. What's the expecation of $N$?
In the book they do the following:
- Let $\ell_i:= h_i\cap h_k$ for $i\in\left\{1,\ldots,k-1\right\}$ be the intersection line of the plane $h_i$ with $h_k$ and $L:=\left\{\ell_1,\ldots, \ell_{k-1}\right\}$
- Let $I:=\left\{i\in\left\{1,\ldots,k-1\right\}:\ell_i\cap t_k\ne\emptyset \right\}$ be the index set of those $\ell_i$ which intersect $t_k$ and $s_i:=\ell_i\cap t_k$ for $i\in I$ be the segment of $\ell_i$ which intersects $t_k$
Now, they state that $N$ is not the number of faces in the arrangement that $\left\{s_i:i\in I\right\}$ induces on $t_k$. Why?
They state the following: Consider the moment where $t_{k-1}$ is treated and assume that $\ell_{k-1}$ intersects $t_k$. The segment $s_{k-1}$ can intersect several faces of the arrangement that $\left\{s_i:i\in I\right\}$ induces on $t_k$. But if such a face $r$ is not incident to one of the edges of $t_k$ (i.e. $r$ is an interior face) then a free split already has been made through this part of $t_k$.
Why is that the case? I absolutely don't understand it.
Their formulation "through this part" is a bit confusing – what they mean is "using this part". Such an interior face doesn't cut anything in the plane outside of itself because it's shielded on all sides by interior edges, and it doesn't cut anything itself because the triangles are non-intersecting; so the moment it's created it would be used for a free split.