Пересечение прямоугольника с множеством прямоугольников (PST)

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

Определение

Priority Search Tree позволяет решать следующую задачу. Даны $n$ точек, а также запросы. Каждый запрос характеризуется отрезком по одной координате $[y_1, y_2]$, а также числом $x_q$ по другой координате. Для каждого запроса структура возвращает все точки, которые находятся в отрезке $[y_1, y_2]$ по одной координате, и имеют другую координату не больше $x_q$. На каждый запрос дерево отвечает за $O(\log\,n + k)$, где $k$ — количество точек в ответе.

Как строится?

Дерево строится рекурсивно. Выберем точку с наименьшей $x$-координатой (если таких несколько, то из них выберем с наименьшим $y$). Все остальные точки отсортируем по $y$ и разобьем на две равные (количество может отличаться на один) части. Далее будем считать, что все точки первой части имеют координату $y$ меньше всех точек второй части (с одинаковыми $y$ поступаем как обычно — сравниваем по $x$). Для каждого из двух множеств, если оно не пусто, построим дерево рекурсивно.

Теорема:

PST занимает $O(n)$ памяти.

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

$\triangleright$

Каждая точка будет корнем ровно одного дерева. Количество деревьев не превышает количества точек. В сумме $O(n)$.

$\triangleleft$

Теорема:

Максимальная глубина PST $O(\log\,n)$.

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

$\triangleright$

При рекурсивном вызове количество точек уменьшается как минимум в два раза.

$\triangleleft$

Теорема:

Построение PST работает за $O(n\log\,n)$ времени.

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

$\triangleright$

Необходимо отсортировать точки по $y$ — для этого необходимо $O(n\log\,n)$. Построение каждого дерева требует $O(k)$, где $k$ — количество точек в дереве, чтобы найти минимальную по $x$ точку, а также для построения новых списков точек для сыновей. На каждом уровне $O(n)$ точек, уровней $O(\log\,n)$, значит, в сумме тоже $O(n\log\,n)$.

$\triangleleft$

Как отвечать на запрос?

Если $x$ корня больше $x_q$, то никакие точки дерева не могут быть в ответе. Будем хранить также минимальную и максимальную по $y$ точки, которые лежат в поддереве. Тогда, если отрезок запроса по $y$ не пересекается с отрезком по $y$ всех точек поддерева, то также никакие точки из дерева не должны быть добавлены в ответ. Если корень дерева лежит в нужном интервале, добавим его в ответ. Вызовем рекурсивно поиск ответа для двух сыновей.

Теорема:

Будет получен правильный ответ на запрос.

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

$\triangleright$

Вроде бы очевидно.

$\triangleleft$

Теорема:

Ответ на запрос работает за $O(\log\,n+k)$, где $k$ — размер ответа.

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

$\triangleright$

Тут все сложнее. Представим, что мы ищем $y_1$ и $y_2$ (из запроса) в PST как в обычном дереве поиска по $y$. Рассмотрим все точки, которые лежат между двумя путями поиска. Среди них рассмотрим точки с $x \lt = x_q$. Ровно эти точки и есть ответ. Разобьем все вершины на три группы. Первая — вершины, которые лежат хотя бы на одном из двух путей. Их $O(\log\,n)$. Вторая — вершины, которые находятся между двумя путями. Третья — все остальные. Время обработки вершин первой группы не превышает $O(\log\,n)$. Как только мы зашли в вершину третей группы, сразу поймем, что отрезок по $y$ не пересекается с запросом и выйдем. А зайти в них мы можем только из вершин, которые лежат на двух путях (а их $O(\log\,n)$). Отлично! Зайдя в вершину второй группы, мы либо ее добавим в ответ и продолжим, либо выйдем, так как единственная причина, почему корень не подошел — его $x$ слишком большой, а, значит, и все вершины поддерева не подходят. В итоге их обработка занимает $O(k)$. В сумме все хорошо!

$\triangleleft$

Псевдокод

 struct PST 
   point root
   point min_y, max_y
   PST *down, *up

 // pts sorted by y
 PST * build_PST(vector<point> pts)
   if (pts.size() == 0)
     return NULL
   min_y = max_ y = root = min_element(pts) // by x
   remove_element(pts, root)
   int mid = pts.size() / 2
   vector<point> down_pts = pts[0..mid]
   vector<point> up_pts = pts[mid+1..pts.size() - 1]
   down = build_PST(down_pts)
   up = build_PST(up_pts)
   if (down != NULL)
     min_y = min(min_y, down->min_y)
   if (up != NULL)
     max_y = max(max_y, up->max_y)

 void req(PST * tree, int y1, int y2, int x_max, vector<point> & ans)
   if (tree == NULL)
     return
   if (x_max < tree->root.x)
     return
   if (y1 > tree->max_y || y2 < tree->min_y)
     return
   if (tree->root in [y1..y2]x[-inf;x_max])
     answer.push_back(tree->root)
   req(tree->down, y1, y2, x_max, ans)
   req(tree->up, y1, y2, x_max, ans)

Причем тут пересечение прямоугольника с множеством прямоугольников?

Задача решается следующим образом. Будем находить ответ тремя разными способами, а их объединение и будет настоящим ответом. Будем считать, что объединение множеств можно делать за $O(n)$, где $n$ — суммарное количество элементов в них.

Первый способ. Найдем все прямоугольники, в которых прямоугольник из запроса лежит полностью. Для этого нужно решать такую задачу. Дано множество прямоугольников, для заданной точки найти все прямоугольники, в которых она лежит. Это точно можно решать за $O(\log^2\,n+answer)$ с помощью двухмерного дерева интервалов. А может можно и проще.

Второй способ. Найдем все прямоугольники, которые полностью лежат внутри заданного в запросе. Для этого воспользуемся range tree. Просто для каждого прямоугольника добавим в range tree его левый верхний угол. Задав запрос в виде нашего прямоугольника, мы получим то, что и нужно.

Третий способ. Найдем все прямоугольники, хотя бы одна сторона которого пересекает заданный в запросе. Для этого воспользуемся деревом отрезков. В структуру добавим все стороны всех прямоугольников и зададим запрос в виде нашего прямоугольника.

Утверждается, что все прямоугольники, которые нам нужны — объединение ответов, полученных тремя способами. Оценивать асимтотику всего этого мне совсем не хочется, но, наверное, это $O(\log^2\,n+answer)$ времени на запрос. $O(n\log\,n)$ памяти из-за range tree и $O(n\log^2\,n)$ на построение. Но, возможно, я что-то забыл или что-то можно сделать более эффективно.