Why is no analysis possible for the 3d version of the random binary space partioning algorithm?

Question

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

1. Randomly shuffle the elements of $S$ such that each possible permutation of those elements has equal probability of appearance
2. If $S$ contains at most one element, create a tree $T$ with value $S$
3. 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\ell^\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\}$
4. Return $T$

Lemma: The expectation of the number $N$ of fragments (a segment might be cut into two fragments by a splitting line) generated by $\text{2dBSP}$ is $\mathcal O(n\ln n)$.

You can skip the proof of the claim, if you know this result.

---

Proof:

• Let $s\in S$ and $N(s)$ be the number of segments in $S$ that are cut when $\ell:=\ell(s)$ is added as the next splitting line
• Claim 1: The expectation of $N(s)$ is at most $2\ln n$
• Proof:
  • For $t\in S\setminus\left\{s\right\}$, let $\operatorname{dist}t$ be the number of segments $u\in S$ between $s$ and $t$ with $u\cap\ell\ne\emptyset$, if $t\cap\ell\ne\emptyset$, and $\infty$ otherwise

• [continuation of the proof]:
  • Let $C(k):=\left\{t\in S\setminus\{s\}:\operatorname{dist}t=k\right\}$ for $k\in\{ 0,\ldots,n-2\}$
  • For all $k$, $C(k+1)\ne\emptyset$ implies $C(k)\ne\emptyset$ and $C(k)$ contains at most $2$ elements
  • Claim 1.1: Let $t\in C(k)$ for some $k$, $u_1,\ldots,u_k\in S\setminus\{s\}$ be the segments between $s$ and $t$ and $E(t)$ be the event that $t$ is cut when $\ell$ is added as the next splitting line. Then the probability of $E(t)$ to occur is at most $1/(k + 2)$
  • Proof:
    • In order for $E(t)$ to occur, $s$ must come before $t$ and $u1, …, uk$ in the random ordering (since $u1,\ldots,uk$ shield $t$ from $s$) and the probability $p(t)$ for that is $1/(k+2)$
    • Moreover, there may be segments that are not cut by $\ell$ but whose extension shields $t$ (and that’s why the claimed expression is not an equality)
  • By (Claim 1.1), the expectation of $N(s)$ is the sum of all $p(t)$ with $t\in S\setminus\{s\}$
  • In the worst case, $\operatorname{dist}t<\infty$ for all $t\in S\setminus\{s\}$
  • Moreover, all distances occur in a consecutive fashion, maybe on both sides of $s$
  • Thus, the sum is bounded by twice the sum of $1/(k+2)$ from $k=0$ to $n-2$, which is twice the $n$th harmonic number minus $1$ and hence bounded by $2\ln n$
• Since $N$ is bounded by $n$ plus the sum of all $N(s)$, we obtain that the expectation of $N$ is bounded by $n+2n\ln n$ by (Claim 1)

---

It's clear that the running time of $\text{2dBSP}$ depends on the number of generated fragments. Using the Lemma above, we can conclude that its expected running time is $\mathcal O(n^2\ln n)$.

Question: $\text{2dBSP}$ can be translated literally into an algorithm $3dBSP$ which processes triangles in the space instead of $S$. However, in the book Computational Geometry: Algorithms and Applications by Mark de Berg et al., the authors state that it's not known how to analyze the expected behavior of $\text{3dBSP}$ theoretically is not possible. Why?

That implies what we cannot bound the number of generated fragments generated by $\text{3dBSP}$ as we did in the Lemma above. So, which step of the proof doesn't work anymore?

Answer 1

There's no longer a linear order on the segments cut by a line, with at most two segments being cut and the others being shielded. A triangle can now cut all other triangles independent of the order in which they are activated. It seems a rather strong statement that "an analysis is not possible", but it's true that the same analysis is not possible.