$\new­com­mand{\R}{\mathbb{R}}\De­clar­e­Math­Op­er­a­tor{\E}{\mathbf{E}}\De­clar­e­Math­Op­er­a­tor{\deg}{deg}$

Here are my orig­i­nal hand-writ­ten notes on this topic.

Sort­ing Line Seg­ments

The idea of sort­ing line seg­ments is mo­ti­vated by the painter's al­go­rithm in com­puter graph­ics. We first want draw things that are far­ther from the viewer and then draw things that are closer to the viewer. This is called depth sort­ing.

For a point $q$, we say that seg­ment $s_1$ is in front of seg­ment $s_2$ (with re­spect to $q$) if there is a ray, $r$, orig­i­nat­ing at $q$ that hits $s_1$ and then $s_2$. We write this as $s_1\prec_q s_2$.

This leads to the fol­low­ing data struc­tures ques­tion that we call scene pre­pro­cess­ing for depth sort­ing:

• Input: A set $S$ of $n$ dis­joint line seg­ments in the plane
• Prob­lem: Pre­process $S$ so that, for any query point $q$ we can quickly sort the el­e­ments of $S$ by the in front of re­la­tion
  

• But this sort­ing is not al­ways pos­si­ble, we can have cy­cles in the $\prec_q$ re­la­tion, 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 seg­ments. For ex­am­ple, 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 prob­lems. It cuts up the input seg­ments so that we can al­ways sort them and it lets us sort quickly.

• Pick a seg­ment $s\in S$ and ex­tend it into a line $\ell$ and store $s$ at the root of the tree
• Cut any line in­ter­sected by $\ell$ into two seg­ments (so now every seg­ment is on ex­actly one side of $\ell$)
  
• Re­cur­sively build BSP trees on the seg­ments to the left of $\ell$ and the seg­ments to the right of $\ell$ and make these the two chil­dren of $s$

With a BSP tree, we can depth-sort 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 re­cur­sively sort the seg­ments in the left sub­tree and the re­cur­sively sort the seg­ments in the right sub­tree. Con­cate­nat­ing these two sorted lists gives a valid depth sort­ing of all the seg­ments, be­cause seg­ments in the right sub­tree can't pos­si­bly be in front of seg­ments in the left sub­tree. This take $O(n+k)$ time, where $k$ is the num­ber of times we cut a seg­ment when con­struct­ing the BSP tree. (Each time we cut a seg­ment we get one more node in our BSP tree.)

If we're not care­ful, we can eas­ily end up with $\Omega(n^2)$ nodes in the BSP tree. (Ex­er­cise: come up with an ex­am­ple where this hap­pens using only ver­ti­cal and hor­i­zon­tal seg­ments)

This is where ran­dom­iza­tion comes to the res­cue. De­fine a ran­dom bi­nary space par­ti­tion tree as a BSP tree in which the root node is cho­sen uni­formly at ran­dom from among all the input seg­ments (and so on, re­cur­sively, when con­struct­ing the sub­trees).

The­o­rem: The ex­pected num­ber of nodes in a ran­dom bi­nary space par­ti­tion tree is $O(n\log n)$

Proof: For each seg­ment $s\in S$, de­fine $X_s$ as the num­ber of seg­ments that get cut when we ex­tend $s$. Then the quan­tity we're study­ing is \[ \E[k] = \E\left[\sum_{s\in S} X_i\right] = \sum_{s\in S}\E[X_s] \en­space . \] So let's focus on a par­tic­u­lar $s\in S$. There are some seg­ments in $S$ that cross the line that we get by ex­tend­ing $s$; these are the seg­ments that might be cut when we ex­tend $s$. Call these $a_1,\ldots,a_k$ and $b_1,\ldots,b_{k'}$ as in the fig­ure below:

Now, de­fine the in­di­ca­tor vari­ables \[ A_i = \begin{cases}1 & \text{if $a_i$ get cut by $s$} \\ 0 &\text{oth­er­wise.} \end{cases} \] and \[ B_i = \begin{cases}1 & \text{if $a_i$ get cut by $s$} \\ 0 &\text{oth­er­wise.} \end{cases} \] So now we have \[ \E[X_s] = \E\left[\sum_{i=1}^k A_i + \sum_{i=1}^{k'} B_i\right] = \sum_{i=1}^k \E[A_i] + \sum_{i=1}^{k'} \E[B_i] \en­space . \] When can $s$ cut $a_i$? This hap­pens when we are build­ing a sub­tree that in­cludes $s$ and $a_1,\ldots,a_i$ and we pick $s$ as the root of that sub­tree. We could also have picked any of $a_1,\ldots,a_i$, so the prob­a­bil­ity that this hap­pens is \[ \Pr\{\text{$s$ cuts $a_i$}\} \le \Pr\{A_i=1\} = \E[A_i] = 1/(i+1) \en­space . \] By the same ar­gu­ment, $\E[B_i] = 1/(i+1)$. Now we can de­ter­mine $\E[X_s]$ with \begin{align*} \E[X_s] & = \sum_{i=1}^k \E[A_i] + \sum_{i=1}^{k'} \E[B_i] \\ & \le \sum_{i=1}^k 1/(i+1) + \sum_{i=1}^{k'} (1/i+1) \\ & = \sum_{i=1}^n 1/(i+1) + \sum_{i=1}^{n'} (1/i+1) \\ & = 2H_n - 2 \le 2 \ln n \en­space . \end{align*} The last line and the in­equal­ity there refer to the har­monic num­bers dis­cussed at the end of the first lec­ture. Fi­nally, sum­ming over all $s$ gives \[ \E[k] = \sum_{s\in S}\E[X_s] \le 2n\ln n \en­space \] and we're done. ∎

Dis­cus­sion

BSP trees are used in ray trac­ing (movie qual­ity com­puter graph­ics), com­puter-as­sisted de­sign soft­ware, and man­u­fac­tur­ing, and other areas.

BSP trees were in­stru­men­tal in mak­ing the orig­i­nal DOOM game run beau­ti­fully on early 90's com­puter hard­ware.

This made id Soft­ware enor­mously suc­cess­ful so they could later bring us Wolfen­stein 3D, Quake, Rage, Orcs and Elves, …