Here are my original handwritten notes on this topic.
Sorting Line Segments
The idea of sorting line segments is motivated by the painter's algorithm in computer graphics. We first want draw things that are farther from the viewer and then draw things that are closer to the viewer. This is called depth sorting.
For a point $q$, we say that segment $s_1$ is in front of segment $s_2$ (with respect to $q$) if there is a ray, $r$, originating at $q$ that hits $s_1$ and then $s_2$. We write this as $s_1\prec_q s_2$.
 Input: A set $S$ of $n$ disjoint line segments in the plane
 Problem: Preprocess $S$ so that, for any query point $q$ we can quickly sort the elements of $S$ by the in front of relation

But this sorting is not always possible, we can have cycles in the $\prec_q$ relation, like $A \prec_q D\prec_q C \prec_q B \prec_q A$.

In cases like this, we have to cut some of the segments. For example, we can cut $A$ into $A_1$ and $A_2$ so that we get $A_1 \prec_q D\prec_q C \prec_q B \prec_q A_2$
BSP Trees
A BSP tree solves both problems. It cuts up the input segments so that we can always sort them and it lets us sort quickly.
 Pick a segment $s\in S$ and extend it into a line $\ell$ and store $s$ at the root of the tree
 Cut any line intersected by $\ell$ into two segments (so now every segment is on exactly one side of $\ell$)
 Recursively build BSP trees on the segments to the left of $\ell$ and the segments to the right of $\ell$ and make these the two children of $s$
With a BSP tree, we can depthsort quickly from any point $q$. The point $q$ is on one side of the root line $\ell$, say the left side. Then we we can recursively sort the segments in the left subtree and the recursively sort the segments in the right subtree. Concatenating these two sorted lists gives a valid depth sorting of all the segments, because segments in the right subtree can't possibly be in front of segments in the left subtree. This take $O(n+k)$ time, where $k$ is the number of times we cut a segment when constructing the BSP tree. (Each time we cut a segment we get one more node in our BSP tree.)
If we're not careful, we can easily end up with $\Omega(n^2)$ nodes in the BSP tree. (Exercise: come up with an example where this happens using only vertical and horizontal segments)
This is where randomization comes to the rescue. Define a random binary space partition tree as a BSP tree in which the root node is chosen uniformly at random from among all the input segments (and so on, recursively, when constructing the subtrees).
Theorem: The expected number of nodes in a random binary space partition tree is $O(n\log n)$
Proof: For each segment $s\in S$, define $X_s$ as the number of segments that get cut when we extend $s$. Then the quantity we're studying is \[ \E[k] = \E\left[\sum_{s\in S} X_i\right] = \sum_{s\in S}\E[X_s] \enspace . \] So let's focus on a particular $s\in S$. There are some segments in $S$ that cross the line that we get by extending $s$; these are the segments that might be cut when we extend $s$. Call these $a_1,\ldots,a_k$ and $b_1,\ldots,b_{k'}$ as in the figure below:
Discussion
BSP trees are used in ray tracing (movie quality computer graphics), computerassisted design software, and manufacturing, and other areas.
BSP trees were instrumental in making the original DOOM game run beautifully on early 90's computer hardware.
This made id Software enormously successful so they could later bring us Wolfenstein 3D, Quake, Rage, Orcs and Elves, …