К-d деревья и перечисление точек в произвольном прямоугольнике (статика) — различия между версиями
Gromak (обсуждение | вклад) (Новая страница: «{{ptready}} == Определение и построение == '''K-d дерево''' (short for k-dimensional tree) {{---}} статическая структ...») |
м (rollbackEdits.php mass rollback) |
||
(не показано 8 промежуточных версий 4 участников) | |||
Строка 1: | Строка 1: | ||
− | {{ | + | {{ready}} |
== Определение и построение == | == Определение и построение == | ||
+ | [[Файл:Kd-tree.png | 500px | thumb | Пример]] | ||
+ | |||
'''K-d дерево''' (short for k-dimensional tree) {{---}} статическая структура данных для хранения точек в <tex>k</tex>-мерном пространстве. Позволяет отвечать на запрос, какие точки лежат в данном прямоугольнике. | '''K-d дерево''' (short for k-dimensional tree) {{---}} статическая структура данных для хранения точек в <tex>k</tex>-мерном пространстве. Позволяет отвечать на запрос, какие точки лежат в данном прямоугольнике. | ||
− | + | Строится это дерево следующим образом: разобьём все точки вертикальной прямой так, чтобы слева (нестрого) и справа (строго) от неё было примерно поровну точек (для этого посчитаем медиану первых координат). Получим подмножества для левого и правого ребёнка. Далее построим для этих подмножеств деревья, но разбивать будем уже не вертикальной, а горизонтальной прямой (для этого посчитаем медиану вторых координат). И так далее (будем считать, что <tex>k = 2</tex> (случай бОльших размерностей обрабатывается аналогично), поэтому на следующем уровне вновь будем разбивать вертикальными прямыми). | |
− | + | ''Замечание: проблемы могут возникнуть, если много точек имеют одинаковую координату, тогда разбить примерно поровну не получится (почти все точки будут лежать на медиане и попадут в левую часть). Лучший способ борьбы с этим {{---}} не вспоминать о данной проблеме совсем. Но вообще с этим борются, используя composite numbers, то есть сравнивая ещё и по другой (другим) координате.'' | |
− | + | Реализовывать построение можно рекурсивно с помощью функции <tex>BuildKdTree(P, Depth)</tex>, принимающей множество точек и глубину. В зависимости от остатка при делении на размерность (при <tex> k = 2 </tex> от чётности размерности) сплитим множество на два подмножества и делаем рекурсивные вызовы. Для лучшего понимания приведём псевдокод: | |
− | |||
− | |||
<code> | <code> | ||
Строка 27: | Строка 27: | ||
</code> | </code> | ||
+ | {{Лемма | ||
+ | |about= | ||
+ | О времени построения | ||
+ | |statement= | ||
+ | Построение выполняется за <tex>O(n \log n)</tex>. | ||
+ | |proof= | ||
+ | Время построения обозначим <tex>T(n)</tex>. Поиск медианы можно сделать за линейное время, поэтому достаточно очевидно, что: | ||
+ | |||
+ | <tex>T(n) = O(1)</tex> if <tex>n = 1</tex>. | ||
+ | |||
+ | <tex>T(n) = O(n) + 2 \cdot T(n / 2)</tex>, otherwise. | ||
+ | |||
+ | Решением этого является <tex>T(n) = O(n \log n)</tex>. | ||
+ | |||
+ | Также стоит отметить, что можно и не искать медиану за линейное время, а просто посортить все точки в самом начале и дальше использовать это. В реализации попроще, асимптотика та же. | ||
+ | }} | ||
+ | |||
+ | {{Лемма | ||
+ | |about= | ||
+ | О занимаемой памяти | ||
+ | |statement= | ||
+ | K-d дерево требует <tex>O(n)</tex> памяти. | ||
+ | |proof= | ||
+ | Высота дерева, очевидно, логарифмическая, а листьев всего <tex>O(n)</tex>. Поэтому будет <tex>O(n)</tex> вершин, каждая занимает <tex>O(1)</tex> памяти. | ||
+ | }} | ||
+ | |||
+ | By the way, если считать <tex>k</tex> константой, то и для случая большей размерности эти оценки будут такими же (доказывается аналогично). | ||
+ | |||
+ | == Запрос == | ||
+ | Пусть нам поступил какой-то прямоугольник <tex>R</tex>. Нужно вернуть все точки, которые в нём лежат. Будем это делать рекурсивно, получая на вход корень дерева и сам прямоугольник <tex>R</tex>. Обозначим область, соответствующую вершине <tex>v</tex>, как <tex>region(v)</tex>. Она будет прямоугольником, одна или более границ которого могут быть на бесконечности. <tex>region(v)</tex> можно явно хранить в узлах, записав при построении, или же считать при рекурсивном спуске. Если корень дерева является листом, то просто проверяем одну точку и при необходимости репортим её. Если нет, то смотрим пересекают ли регионы детей прямоугольник <tex>R</tex>. Если да, то запускаемся рекурсивно от такого ребёнка. При этом, если регион полностью содержится в <tex>R</tex>, то можно репортить сразу все точки из него. Тем самым мы, очевидно, вернём все нужные точки и только их. Чтобы стало совсем понятно, приведём псевдокод: | ||
+ | |||
+ | <code> | ||
+ | SearchKdTree(v, R) | ||
+ | //Input. The root of (a subtree of) a kd-tree, and a range R. | ||
+ | //Output. All points at leaves below v that lie in the range. | ||
+ | if v is a leaf | ||
+ | Report the point stored at v if it lies in R. | ||
+ | else | ||
+ | if region(v.left) is fully contained in R | ||
+ | ReportSubtree(v.left) | ||
+ | else if region(v.left) intersects R | ||
+ | SearchKdTree(v.left, R) | ||
+ | if region(v.right) is fully contained in R | ||
+ | ReportSubtree(v.right) | ||
+ | else if region(v.right) intersects R | ||
+ | SearchKdTree(v.right, R) | ||
+ | </code> | ||
+ | |||
+ | Здесь <tex>ReportSubtree</tex> репортит все точки в поддереве. | ||
+ | |||
+ | By the way, точно так же можно перечислять точки в любом множестве, ведь нигде не используется, что <tex>R</tex> {{---}} прямоугольник. | ||
+ | |||
+ | {{Теорема | ||
+ | |about= | ||
+ | О времени на запрос | ||
+ | |statement= | ||
+ | Перечисление точек в прямоугольнике выполняется за <tex>O(\sqrt n + ans)</tex>, где <tex>ans</tex> {{---}} размер ответа. | ||
+ | |proof= | ||
+ | Сперва заметим, что все <tex>ReportSubtree</tex> суммарно выполняются за <tex>O(ans)</tex>. Поэтому достаточно доказать оценку для числа рекурсивных вызовов. А рекурсивные вызовы выполняются только для тех вершин, регионы которых пересекают <tex>R</tex>, но не содержатся в нём. Такие регионы обязательно пересекают хотя бы одну (axis-parallel) сторону заданного прямоугольника. Оценим количество регионов, которые могут пересекаться произвольной вертикальной прямой. Для горизонтальной прямой это будет аналогично. | ||
+ | |||
+ | Обозначим максимально возможное количество регионов, пересекаемых какой-либо вертикальной прямой, в дереве для <tex>n</tex> точек, у которого первое разбиение делается вертикальной прямой, как <tex>Q(n)</tex>. Рассмотрим произвольную вертикальную прямую <tex>l</tex>. Она будет пересекать регион корня и какого-то одного из его детей (например, левого). При этом ни один из регионов в другом (правом) поддереве пересекать она не может. Левая половина разбита ещё на 2 части горизонтальной прямой, в каждой из них примерно <tex>n / 4</tex> вершин, и они хранятся в поддереве, у которого первое разбиение делается вертикальной прямой. Это даёт нам следующее соотношение: | ||
+ | |||
+ | <tex>Q(n) = O(1)</tex> if <tex>n = 1</tex>. | ||
+ | |||
+ | <tex>Q(n) = 2 + 2 \cdot Q(n / 4)</tex>, otherwise. | ||
+ | Глубина дерева рекурсии равна <tex>\log_4 n = \frac{1}{2}\log_2 n</tex> | ||
+ | Следовательно, <tex>Q(n) = O(2^{\frac{1}{2}\log_2 n}) = O(\sqrt n)</tex> является решением. Принимая во внимание всё, что писалось выше, получаем требуемое. | ||
+ | }} | ||
+ | By the way, в общем случае время на запрос <tex>O(n^{1 - 1/k} + ans)</tex> из соотношения <tex>Q(n) = k + 2^{k - 1} \cdot Q(n / 2^k)</tex>. | ||
== Ссылки == | == Ссылки == |
Текущая версия на 19:40, 4 сентября 2022
Конспект готов к прочтению. |
Определение и построение
K-d дерево (short for k-dimensional tree) — статическая структура данных для хранения точек в
-мерном пространстве. Позволяет отвечать на запрос, какие точки лежат в данном прямоугольнике.Строится это дерево следующим образом: разобьём все точки вертикальной прямой так, чтобы слева (нестрого) и справа (строго) от неё было примерно поровну точек (для этого посчитаем медиану первых координат). Получим подмножества для левого и правого ребёнка. Далее построим для этих подмножеств деревья, но разбивать будем уже не вертикальной, а горизонтальной прямой (для этого посчитаем медиану вторых координат). И так далее (будем считать, что
(случай бОльших размерностей обрабатывается аналогично), поэтому на следующем уровне вновь будем разбивать вертикальными прямыми).Замечание: проблемы могут возникнуть, если много точек имеют одинаковую координату, тогда разбить примерно поровну не получится (почти все точки будут лежать на медиане и попадут в левую часть). Лучший способ борьбы с этим — не вспоминать о данной проблеме совсем. Но вообще с этим борются, используя composite numbers, то есть сравнивая ещё и по другой (другим) координате.
Реализовывать построение можно рекурсивно с помощью функции
, принимающей множество точек и глубину. В зависимости от остатка при делении на размерность (при от чётности размерности) сплитим множество на два подмножества и делаем рекурсивные вызовы. Для лучшего понимания приведём псевдокод:
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 subsetsand with a vertical line through the median x-coordinate of the points in P else Split P into two subsets and with a horizontal line through the median y-coordinate of the points in P. <- BuildKdTree( , Depth + 1) <- BuildKdTree( , Depth + 1) Create a node v storing , make the left child of v, and make the right child of v. return v
Лемма (О времени построения): |
Построение выполняется за . |
Доказательство: |
Время построения обозначим . Поиск медианы можно сделать за линейное время, поэтому достаточно очевидно, что:if . , otherwise. Решением этого является Также стоит отметить, что можно и не искать медиану за линейное время, а просто посортить все точки в самом начале и дальше использовать это. В реализации попроще, асимптотика та же. . |
Лемма (О занимаемой памяти): |
K-d дерево требует памяти. |
Доказательство: |
Высота дерева, очевидно, логарифмическая, а листьев всего | . Поэтому будет вершин, каждая занимает памяти.
By the way, если считать
константой, то и для случая большей размерности эти оценки будут такими же (доказывается аналогично).Запрос
Пусть нам поступил какой-то прямоугольник
. Нужно вернуть все точки, которые в нём лежат. Будем это делать рекурсивно, получая на вход корень дерева и сам прямоугольник . Обозначим область, соответствующую вершине , как . Она будет прямоугольником, одна или более границ которого могут быть на бесконечности. можно явно хранить в узлах, записав при построении, или же считать при рекурсивном спуске. Если корень дерева является листом, то просто проверяем одну точку и при необходимости репортим её. Если нет, то смотрим пересекают ли регионы детей прямоугольник . Если да, то запускаемся рекурсивно от такого ребёнка. При этом, если регион полностью содержится в , то можно репортить сразу все точки из него. Тем самым мы, очевидно, вернём все нужные точки и только их. Чтобы стало совсем понятно, приведём псевдокод:
SearchKdTree(v, R) //Input. The root of (a subtree of) a kd-tree, and a range R. //Output. All points at leaves below v that lie in the range. if v is a leaf Report the point stored at v if it lies in R. else if region(v.left) is fully contained in R ReportSubtree(v.left) else if region(v.left) intersects R SearchKdTree(v.left, R) if region(v.right) is fully contained in R ReportSubtree(v.right) else if region(v.right) intersects R SearchKdTree(v.right, R)
Здесь
репортит все точки в поддереве.By the way, точно так же можно перечислять точки в любом множестве, ведь нигде не используется, что
— прямоугольник.Теорема (О времени на запрос): |
Перечисление точек в прямоугольнике выполняется за , где — размер ответа. |
Доказательство: |
Сперва заметим, что все суммарно выполняются за . Поэтому достаточно доказать оценку для числа рекурсивных вызовов. А рекурсивные вызовы выполняются только для тех вершин, регионы которых пересекают , но не содержатся в нём. Такие регионы обязательно пересекают хотя бы одну (axis-parallel) сторону заданного прямоугольника. Оценим количество регионов, которые могут пересекаться произвольной вертикальной прямой. Для горизонтальной прямой это будет аналогично.Обозначим максимально возможное количество регионов, пересекаемых какой-либо вертикальной прямой, в дереве для точек, у которого первое разбиение делается вертикальной прямой, как . Рассмотрим произвольную вертикальную прямую . Она будет пересекать регион корня и какого-то одного из его детей (например, левого). При этом ни один из регионов в другом (правом) поддереве пересекать она не может. Левая половина разбита ещё на 2 части горизонтальной прямой, в каждой из них примерно вершин, и они хранятся в поддереве, у которого первое разбиение делается вертикальной прямой. Это даёт нам следующее соотношение:if . , otherwise. Глубина дерева рекурсии равна Следовательно, является решением. Принимая во внимание всё, что писалось выше, получаем требуемое. |
By the way, в общем случае время на запрос
из соотношения .Ссылки
- van Kreveld, de Berg, Overmars, Cheong — Computational Geometry. Algorithms and Applications. Страница 99.
- Английская Википедия
- Русская Википедия