Изменения
→Построение BSP-дерева
'''BSPTree''' 2D_BSP_tree(<tex>S</tex>):
'''if''' <tex>|S| \leqslant 1</tex>
<tex>T \leftarrow</tex> '''BSPTree'''(<tex>S</tex>) <font color="green">/* <tex>T</tex> будет листом, в котором хранится данное множество */</font>
'''return''' <tex>T</tex>
'''else''' <font color="green">/* используем <tex>l(s_1)</tex> как разбивающую прямую */</tex></font>
Пусть <tex>k = \mathrm{dist}(s_i,\ s_j)</tex> и <tex>s_{j_1},\ s_{j_2},\ \ldots ,\ s_{j_k}</tex> {{---}} отрезки между <tex>s_i</tex> и <tex>s_j</tex>.
Найдём вероятность того, что при добавлении <tex>l(s_i)</tex> разрежет <tex>s_j</tex>. Чтобы это произошло, <tex>s_i</tex> должен быть рассмотрен перед <tex>s_j</tex> и перед любым из отрезков между <tex>s_i</tex> и <tex>s_j</tex>, иначе они бы защитили <tex>s_j</tex> от <tex>s_i</tex>. Другими словами, среди множества индексов <tex>\{i, \ j, \ j_1, ... \ \ldots , \ j_k\}</tex> индекс <tex>i</tex> должен быть наименьшим.
Так как отрезки расположены в случайном порядке, получаем:
'''BSPTree''' 3D_BSP_tree(<tex>S</tex>):
'''if''' <tex>|S| \leqslant 1</tex>
<tex>T \leftarrow</tex> '''BSPTree'''(<tex>S</tex>) <font color="green">/* <tex>T</tex> будет листом, в котором хранится данное множество */</font>
'''return''' <tex>T</tex>
'''else''' <font color="green">/* используем <tex>h(t_1)</tex> как разбивающую плоскость */</font>
