Изменения
Нет описания правки
Размер полученного BSP-дерева снова зависит от порядка треугольников. Как и в двухмерном случае, мы можем попытаться получить хороший ожидаемый размер дерева, переставив треугольники в случайном порядке. На практике это дает хорошие результаты.
== См. также ==
* [[Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree)]]
* [[Дерево интервалов (interval tree) и пересечение точки с множеством интервалов]]
* [[Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree)]]
== Источники иформации ==
* Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000), Computational Geometry (2nd revised ed.), Springer-Verlag, ISBN 3-540-65620-0 Chapter 12: Binary Space Partition: pp.259–267.
