Why do at least half of all random orderings generate a binary space partition of size $n+4n\ln n$ in the random binary space partition algorithm? Let $S$ be a finite ordered set of non-intersecting finite line segments in the plane. Let's randomly shuffle the elements of $S$ such that each possible permutation of those elements has equal probability of appearance.
Suppose we choose the first element $s_1$ of $S$, split the plane by the infinite extension $\ell=\ell(s_1)$ (called a splitting line) of $s_1$ into a half-plane $\ell^+$ above and $\ell^-$ below $\ell$ and recursively continue this process for both of the subsets of $S$ induced by $\ell^+$ and $\ell^-$.
The splitting lines may cut segments into fragments. The process described above continues until there is only one fragment in the interior of each region induced by the surrounding splitting lines. The result is called binary space partition. I hope the following figure will illustrate the result of this process:
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;$

We can show that $$\Pr\left[t\text{ is cut when }\ell(s)\text{ is added as the next splitting line}\right]\le\frac 1{\operatorname{dist}_st+2}$$ for all $s\in S$ and $t\in S\setminus\left\{s\right\}$ where $$\operatorname{dist}_st:=\begin{cases}\text{# segments }u\in S\text{ between }s\text{ and }t\text{ with }\ell(s)\cap u\ne\emptyset&\text{, if }\ell(s)\cap t\ne\emptyset\\\infty&\text{, otherwise}\end{cases}$$ for $s\in S$ and $t\in S\setminus\left\{s\right\}$.

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;$

Thus, $$\operatorname E\left[\text{# cuts generated by }s\right]\le\sum_{t\in S\setminus\left\{s\right\}}\frac 1{\operatorname{dist}_st+2}\le 2\ln n$$ for all $s\in S$ and the expected total number of generated fragments is bounded by $n+2n\ln n$ (since we start with $n$ segments).

Question: Why can we conclude that


*

*a binary space partition of size ($:=$ number of generated fragments) $n+2n\ln n$ exists?

*at least half of all random orderings lead to a binary space partition of size $n+4n\ln n$?


Both statements can be found in Computational Geometry: Algorithms and Applications by Mark de Berg, below the proof of Lemma 12.1 and I absolutely don't understand why they are true.

The statements in the book are correct if you interpret "of size" to mean "of size at most". Taken literally, they are clearly false.
