Изменения

Пусть <tex>S </tex> {{- --}} множество из <tex>n </tex> непересекающихся отрезков на плоскости. Ограничимся авто-разбиением, рассматривая только прямые, содержащие один из отрезков.

Пусть <tex>l(s) </tex> {{- --}} прямая, содержащая отрезок <tex>s</tex>.

На вход алгоритму подается <tex>S = {s1s_1, s2s_2, ... sn, s_n} - множество отрезков. BSPTree 2D_BSP_tree(S) if |S| <= 1 Create a tree T consisting of a single leaf node, where the set S is stored explicitly. return T else /* Use l(s1) as the splitting line */ S+ \leftarrow tex> {s \пересечь l(s1)+ : s \in S}; T+ \leftarrow 2D_BSP_tree(S+); S− \leftarrow {s \пересечь l(s1)− : s ∈ S---}; T− \leftarrow 2D_BSP_tree(S−); Create a BSP tree T with root node ν, left subtree T−, right subtree T+, and with S(ν) = {s \in S : s \subset l(s1)}множество отрезков. return T

Понятно BSPTree 2D_BSP_tree(<tex>S</tex>) if <tex>|S| <= 1</tex> <tex>T \leftarrow</tex> new BSPTree(S) /* <tex>T</tex> будет листом, в котором хранится данное множество */ return <tex>T</tex> else /* используем <tex>l(s1)</tex> как разбивающую прямую */ <tex>S^+ \leftarrow \{s \cap l^+(s_1) : s \in S\}</tex> <tex>T^+ \leftarrow</tex> 2D_BSP_tree(<tex>S^+</tex>) <tex>S^− \leftarrow \{s \cap l^-(s_1) : s \in S\}</tex> <tex>T^- \leftarrow</tex> 2D_BSP_tree(<tex>S^−</tex>) <tex>S_v \leftarrow \{s \in S : s \subset l(s_1)\}</tex> <tex>T \ leftarrow</tex> new BSPTree(S_v, что алгоритм создает T^-, T^+) // создаем BSP-дерево для множества Sc корнем в вершине <tex>v</tex>, но будет ли оно наименьшим?левым поддеревом <tex>T^−</tex> и правым поддеревом <tex>T^+</tex> // и множеством хранимых объектов <tex>S_v</tex> return <tex>T</tex>

НаверноеПонятно, стоит тщательней выбирать прямую разбиения, а не просто брать l(s1). Возможным подходом является выбор отрезка s \in S, такого что l(s) пересекает наименьшее число отрезков. Но такой жадный алгоритм работает не на всех конфигурациях отрезков. Кроме тогосоздает BSP-дерево для множества <tex>S</tex>, поиск такого отрезка - занятие затратное.но будет ли оно наименьшим?

Как и в других алгоритмахНаверное, когда нужно сделать сложный выборстоит тщательней выбирать прямую разбиения, а не просто выберем случайнобрать <tex>l(s_1)</tex>. Это означаетВозможным подходом является выбор отрезка <tex>s \in S</tex>, такого что для разбиения мы будем использовать рандомный отрезок<tex>l(s)</tex> пересекает наименьшее число отрезков. Но такой жадный алгоритм работает не на всех конфигурациях отрезков. Для этого перед тем, как начинать построение дереваКроме того, расположим отрезки в S случайном порядкепоиск такого отрезка {{---}} занятие затратное.

Как и в других алгоритмах, когда нужно сделать сложный выбор, просто выберем случайно. Это означает, что для разбиения мы будем использовать рандомный отрезок. Для этого перед тем, как начинать построение дерева, расположим отрезки в <tex>S</tex> случайном порядке.  2D_random_BSP_tree(<tex>S</tex>) <tex>S \leftarrow </tex> random_permutation(<tex>S</tex>). <tex>T \leftarrow </tex> 2D_BSP_tree(<tex>S</tex>) return <tex>T</tex>

Рассмотрим одну из таких поверхностей <tex>f</tex>. В <tex>S </tex> могут быть отрезки, которые полностью пересекают <tex>f</tex>. Выбор одного из таких отрезков для разбиения <tex>f </tex> не вызовет фрагментации других отрезков внутри <tex>f</tex>, так как данный отрезок исключается из дальнейшего рассмотрения.Назовем такое свободным разбиением.

Теперь оценим производительность алгоритма 2D_random_BSP_tree. Для упрощения рассуждений будем анализировать версию без свободных разбиений (асимптотической разницы они не дают). Начнем с анализа размера BSP-дерева, равного числу полученных фрагментов, которое зависит от сгенерированной перестановки отрезков. Некоторые перестановки могут породить маленькие деревья, а другие {{- --}} большие.

В качестве примера рассмотрим три отрезка, изображенные на рисунке. Если они рассматриваются в порядке (a), то мы получаем пять фрагментов, если же в порядке (b) {{- --}} то всего три фрагмента.

Так как размер BSP-дерева зависит от сгенерированной перестановки, будем анализировать ожидаемый размер BSP-дерева {{- --}} средний размер для всех <tex>n! </tex> перестановок.

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

Пусть <tex>s_i </tex> {{- --}} фиксированный отрезок из <tex>S</tex>. Проанализируем ожидаемое количество отрезков, которые мы разрежем, когда <tex>l(s_i) </tex> будет добавлена алгоритмом как следующая разбивающая прямая.

Рассмотрим рисунок и постараемся понять разрезается ли отрезок <tex>s_j </tex> при добавлении прямой <tex>l(s_i)</tex>, в зависимости от отрезков, которые разрезаны <tex>l(s_i)</tex>, но находятся между <tex>s_i </tex> и <tex>s_j</tex>.

В частности, когда прямая, пересекающая такой отрезок, добавляется раньше <tex>l(s_i)</tex>, она закрывает <tex>s_j </tex> от <tex>s_i</tex>. На рисунке (b) так происходит с отрезком <tex>s_3</tex>, который защищен отрезком <tex>s_1 </tex> от <tex>s_2</tex>.

Эти размышления приводят нас к определению расстояния от какого-то отрезка до фиксированного отрезка <tex>s_i</tex>.

dist_s_i<tex>dist_{s_i}(s_j) </tex> = {количество пересекаемых отрезков, если <tex>l(s_i) </tex> пересекает <tex>s_j</tex>; +inf<tex>infinity</tex>, иначе}

Для всех конечных расстояний до отрезка <tex>s_i </tex> может быть только два отрезка с одинаковым расстоянием {{- --}} те, что лежат по разные стороны от <tex>s_i</tex>.

Пусть <tex>k = dist_s_idist_{s_i}(s_j) </tex> и s_j_1<tex>s_{j_1}, s_j_2s_{j_2}, ... s_j_k , 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>s_j) <= 1 / (k + 2)</tex>

Существуют отрезки, которые не разрезаются <tex>l(s_i)</tex>, но расширение которых защитит <tex>s_j</tex>, так что выше записано неравенство.

Теперь мы можем ограничить ожидаемое число разрезов, происходящих при добавлении <tex>s_i</tex>:<tex>E(</tex>число разрезов, происходящих при добавлении <tex>s_i) <= sum(i != j, 1 / (k + 2)) <= 2 * sum(k=0..n - 2, 1/ (k + 2)) <= 2 * ln n</tex>.

По линейности ожиданий мы можем заключить, что ожидаемое число разрезов, вызванных добавлением всех отрезков составляет не более <tex>2nlogn</tex>. Так как изначально даны n отрезков, ожидаемое число фрагментов ограничено <tex>n + 2nlogn</tex>.

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

Теперь проанализируем время работы алгоритма. Понятно, что оно зависит от используемой перестановки, так что опять рассмотрим ожидаемое время работы. Нахождение рандомной перестановки занимает <tex>O(n)</tex>. Если проигнорировать время рекурсивных вызовов, то время работы алгоритма линейно от количества фрагментов в <tex>S</tex>. Это число не превышает <tex>n</tex>, так как становится меньше с каждым рекурсивным вызовом. Число рекурсивных вызовов ограничено количеством сгенерированных фрагментов, которое составляет <tex>O(nlogn)</tex>. Таким образом, время построения дерева составляет <tex>O(n^2logn)</tex>.

| statement = BSP-дерево размера <tex>O(nlogn) </tex> может быть построено за ожидаемое время <tex>O(n^2logn)</tex>.

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

Для треугольника <tex>t </tex> обозначим плоскость, содержащую его, как <tex>h(t)</tex>.На вход алгоритму подается множество треугольников <tex>S = \{t1t_1, t2t_2, . . . ,tnt_n\}</tex>, заданных в трехмерном пространстве.

BSPTree 3DBSP3D_BSP_tree(<tex>S</tex>) if <tex>|S| <= 1</tex> Create a tree <tex>T \leftarrow</tex> new BSPTree(S) /* <tex>T consisting of a single leaf node</tex> будет листом, where the set S is stored explicitly.в котором хранится данное множество */ return <tex>T</tex> else /* Use используем <tex>h(t1) as the splitting plane. </tex> как разбивающую плоскость */ <tex>S^+ \leftarrow \{t \пересечь cap h^+(t1t_1)+ : t ∈ \in S\}</tex> <tex>T^+ \leftarrow 3DBSP</tex> 3D_BSP_tree(<tex>S^+</tex>) S− <tex>S^− \leftarrow\{t \пересечь cap h^-(t1t_1)− : t ∈ \in S\}</tex> T− <tex>T^− \leftarrow 3DBSP</tex>3D_BSP_tree(S−<tex>S^−</tex>) Create a BSP tree T with root node ν, left subtree T−, right subtree T+, and with S(ν) = <tex>S_v \leftarrow \{t ∈ \in S : t ⊂ \subset h(t1t_1)\}.</tex> <tex>T \ leftarrow</tex> new BSPTree(S_v, T^-, T^+) // создаем BSP-дерево c корнем в вершине <tex>v</tex>, левым поддеревом <tex>T^−</tex> и правым поддеревом <tex>T^+</tex> // и множеством хранимых объектов <tex>S_v</tex> return <tex>T</tex>