К-d деревья и перечисление точек в произвольном прямоугольнике (статика)

Конспект написан не до конца, но основные вещи уже есть.

Определение и построение

Пример

K-d дерево (short for k-dimensional tree) — статическая структура данных для хранения точек в [math]k[/math]-мерном пространстве. Позволяет отвечать на запрос, какие точки лежат в данном прямоугольнике.

Примечание: в книжке описывается двумерный вариант, и на лекциях, кажется, только он был, поэтому далее считается, что [math]k = 2[/math]. Обобщение на большую размерность достаточно просто додумать при необходимости. Местами будет упомянут и случай [math]k \gt 2[/math].

Строится это дерево следующим образом: разобьём все точки вертикальной прямой так, чтобы слева (нестрого) и справа (строго) от неё было примерно поровну точек (для этого посчитаем медиану первых координат). Получим подмножества для левого и правого ребёнка. Далее построим для этих подмножеств деревья, но разбивать будем уже не вертикальной, а горизонтальной прямой (для этого посчитаем медиану вторых координат). И так далее (раз считаем, что [math]k = 2[/math], то на следующем уровне вновь будем разбивать вертикальными прямыми).

Замечание: проблемы могут возникнуть, если много точек имеют одинаковую координату, тогда разбить примерно поровну не получится (почти все точки будут лежать на медиане и попадут в левую часть). Лучший способ борьбы с этим — не вспоминать о данной проблеме совсем. Но вообще с этим борются, используя composite numbers, то есть сравнивая ещё и по другой (другим) координате. Не думаю, что об этом нужно много писать.

Реализовывать построение можно рекурсивно с помощью функции [math]BuildKdTree(P, Depth)[/math], принимающей множество точек и глубину. В зависимости от остатка при делении на размерность (в нашем случае от чётности) сплитим множество на два подмножества и делаем рекурсивные вызовы. Для лучшего понимания приведём псевдокод:

BuildKdTree(P, Depth)
//Input. A set of points P and the current depth Depth.
//Output. The root of a kd-tree storing P.
if P contains only one point
   return a leaf storing this point
else if depth is even
   Split P into two subsets [math]P_1[/math] and [math]P_2[/math] with a vertical line [math]l[/math] through the median x-coordinate of the points in P
else 
   Split P into two subsets [math]P_1[/math] and [math]P_2[/math] with a horizontal line [math]l[/math] through the median y-coordinate of the points in P. 
[math]V_{left}[/math] <- BuildKdTree([math]P_1[/math], Depth + 1)
[math]V_{right}[/math] <- BuildKdTree([math]P_2[/math], Depth + 1)
Create a node v storing [math]l[/math], make [math]V_{left}[/math] the left child of v, and make [math]V_{right}[/math] the right child of v.
return v 

Лемма (О времени построения):

Построение выполняется за [math]O(n \log n)[/math].

Доказательство:

[math]\triangleright[/math]

Время построения обозначим [math]T(n)[/math]. Поиск медианы можно сделать за линейное время, поэтому достаточно очевидно, что: [math]T(n) = O(1)[/math] if [math]n = 1[/math]. [math]T(n) = O(n) + 2 \cdot T(n / 2)[/math], otherwise. Умные люди могут сразу же заметить, что решением этого является [math]T(n) = O(n \log n)[/math]. А люди моего уровня могут почитать умные книжки или просто поверить в данный факт. Также стоит отметить, что можно и не искать медиану за линейное время, а просто посортить все точки в самом начале и дальше использовать это. В реализации попроще, асимптотика та же.

[math]\triangleleft[/math]

Лемма (О занимаемой памяти):

K-d дерево требует [math]O(n)[/math] памяти.

Доказательство:

[math]\triangleright[/math]

Высота дерева, очевидно, логарифмическая, а листьев всего [math]O(n)[/math]. Поэтому будет [math]O(n)[/math] вершин, каждая занимает [math]O(1)[/math] памяти.

[math]\triangleleft[/math]

Запрос

Ы

Ссылки

• van Kreveld, de Berg, Overmars, Cheong — Computational Geometry. Algorithms and Applications. Страница 99.
• Английская Википедия
• Русская Википедия