Изменения

Данную задачу можно элегантно решить при помощи техники '''двоичного разбиения пространства''' (англ. ''binary space partion, BSP'').

Чтобы понять, что из себя представляет двоичное разбиение пространства, рассмотрим рисунок. На нем показано двоичное разбиение множества объектов на плоскости и дерево, которое этому разбиению соответствует.

В двумерном случае BSP строится с помощью рекурсивного разбиения плоскости прямыми. В данном примере это происходит так: сначала проводим прямую <tex>l_1</tex>, разбивая полуплоскость выше <tex>l_1</tex> прямой <tex>l_2</tex>, а ниже {{---}} прямой <tex>l_3</tex> и так далее.