Изменения

| statement = Ожидаемое число фрагментов, сгенерированных алгоритмом '''2D_random_BSP_tree ''' есть <tex>\mathcal{O}(n \log n)</tex>.

<tex>dist_\mathrm{s_idist}(s_i,\ s_j)</tex> = \left\{\begin{array}{количество пересекаемых отрезков, если <tex>llcl}|\{s_j \mid l(s_i) \cap s_j \}| & \mathrm{if}\ l(s_i)</tex> пересекает <tex>\cap s_j\ne \varnothing \\\infty & \mathrm{otherwise} \\\end{array}\right.</tex>; <tex>infinity</tex>, иначе}

Пусть <tex>k = dist_\mathrm{s_idist}(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, ... , j_k\}</tex> индекс <tex>i</tex> должен быть наименьшим.

<tex>P(l(s_i)</tex> разрезает <tex>\cap s_j\ne \varnothing) <= \leqslant \genfrac{}{}{}{0}{1 / (}{k + 2)}</tex>

<tex>E(</tex>число разрезов, происходящих при добавлении <tex>s_i) \leqslant \sum\limits_{i \ne j} \genfrac{}{}{}{0}{1}{k + 2} \leqslant 2 \cdot \sum\limits_{k=0}^{n - 2} \genfrac{}{}{}{0}{1}{k + 2} \leqslant 2 \ln n</tex>. По линейности ожиданий мы можем заключить, что ожидаемое число разрезов, вызванных добавлением всех отрезков составляет не более <tex>2nlogn2n\log n</tex>. Так как изначально даны <tex>n </tex> отрезков, ожидаемое число фрагментов ограничено <tex>n + 2nlogn2n\log n</tex>.

Мы показалиБыло показано, что ожидаемый размер BSP-дерева, построенного с помощью алгоритма '''2D_random_BSP_tree''', составляет <tex>n + 2nlogn2n\log n</tex>. Следовательно, мы доказали, что BSP-дерево размера <tex>n + 2nlogn2n\log n</tex> существует для любого множества <tex>n</tex> отрезков. Кроме того, хотя бы половина перестановок приводит к BSP-дереву размера <tex>n + 4nlogn4n\log n</tex>.

Теперь проанализируем время работы алгоритма. Понятно, что оно зависит от используемой перестановки, так что опять рассмотрим ожидаемое время работы. Нахождение рандомной перестановки занимает <tex>\mathcal{O}(n)</tex>при помощи [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса |алгоритма Фишера-Йетса]]. Если проигнорировать время рекурсивных вызовов, то время работы алгоритма линейно от количества фрагментов в <tex>S</tex>. Это число не превышает <tex>n</tex>, так как становится меньше с каждым рекурсивным вызовом. Число рекурсивных вызовов ограничено количеством сгенерированных фрагментов, которое составляет <tex>\mathcal{O}(nlognn\log n)</tex>. Таким образом, время построения дерева составляет <tex>\mathcal{O}(n^2logn2\log n)</tex>.

| statement = BSP-дерево размера <tex>\mathcal{O}(nlognn\log n)</tex> может быть построено за ожидаемое время <tex>\mathcal{O}(n^2logn2\log n)</tex>.

Описанный выше алгоритм легко распространяется обобщается на трёхмерное пространство. Как было упомянуто выше, мы считаем, что работаем в 3D с двухмерного пространства на трехмерноетриангуляцией граней многранников.

Пусть <tex>S</tex> {{---}} множество непересекающихся треугольков в <tex>\mathbb{R}^3</tex>.

На вход алгоритму подается множество треугольников <tex>S = \{t_1, \ t_2, ... \ \dots , \ t_n\}</tex>, заданных в трехмерном пространстве.

'''BSPTree ''' 3D_BSP_tree(<tex>S</tex>): '''if ''' <tex>|S| <= 1</tex> <tex>T \leftarrow</tex> new '''BSPTree'''(S) <font color="green">/* <tex>T</tex> будет листом, в котором хранится данное множество */</font> '''return ''' <tex>T</tex> '''else ''' <font color="green">/* используем <tex>h(t1t_1)</tex> как разбивающую плоскость */</font> <tex>S^+ \leftarrow \{t \cap h^+(t_1) : \mid t \in S\}</tex> <tex>T^+ \leftarrow</tex> 3D_BSP_tree(<tex>S^+</tex>) <tex>S^− - \leftarrow \{t \cap h^-(t_1) : \mid t \in S\}</tex> <tex>T^− - \leftarrow </tex>3D_BSP_tree(<tex>S^−-</tex>) <tex>S_v \leftarrow \{t \in S : \mid t \subset h(t_1)\}</tex> <tex>T \ leftarrow</tex> new '''BSPTree'''(<tex>S_v, \ T^-, \ T^+</tex>) <font color="green">// создаем BSP-дерево c корнем в вершине <tex>v</tex>, левым поддеревом <tex>T^−-</tex> и правым поддеревом <tex>T^+</tex> </font> <font color="green">// и множеством хранимых объектов <tex>S_v</tex></font> '''return ''' <tex>T</tex>