Изменения

Есть множество точек на плоскости. Нужно найти две самые удалённые из них[[Файл:Kd-tree.png | 400px | right]]

[[Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull|Найдём выпуклую оболочку]] исходного множества и получим более простую задачу: найти две наиболее удалённые вершины в выпуклом многоугольнике. Сделать это можно за линейное время с помощью метода, который называется '''вращающиеся калиперыK-d дерево''' (англshort for k-dimensional tree) {{---}} статическая структура данных для хранения точек в <tex>k</tex>-мерном пространстве. ''rotating calipers''Позволяет отвечать на запрос, какие точки лежат в данном прямоугольнике.Строится это дерево следующим образом: разобьём все точки вертикальной прямой так, чтобы слева (нестрого) и справа (строго) от неё было примерно поровну точек (для этого посчитаем медиану первых координат). Получим подмножества для левого и правого ребёнка. Далее построим для этих подмножеств деревья, но разбивать будем уже не вертикальной, а горизонтальной прямой (для этого посчитаем медиану вторых координат). И так далее (будем считать, что <tex>k = 2</tex> (случай бОльших размерностей обрабатывается аналогично), поэтому на следующем уровне вновь будем разбивать вертикальными прямыми).

''ОбоснованиеЗамечание: Пусть диаметр с одной стороны содержит точкупроблемы могут возникнуть, если много точек имеют одинаковую координату, которая тогда разбить примерно поровну не принадлежит выпуклой оболочкеполучится (почти все точки будут лежать на медиане и попадут в левую часть). Тогда продлим диаметр в эту сторону до пересечения Лучший способ борьбы с выпуклой оболочкойэтим {{---}} не вспоминать о данной проблеме совсем. ОчевидноНо вообще с этим борются, он станет длиннее. А потом заметим, что диаметр станет еще больше, если сдвинуть его к одному из концов ребраиспользуя composite numbers, в которое мы уперлись. Конецто есть сравнивая ещё и по другой (другим) координате.''

== Постановка задачи ==Пусть Реализовывать построение можно рекурсивно с помощью функции <tex>BuildKdTree(P , Depth)</tex>, принимающей множество точек и глубину. В зависимости от остатка при делении на размерность (при <tex> k = 2 </tex> от чётности размерности) сплитим множество на два подмножества и делаем рекурсивные вызовы. Для лучшего понимания приведём псевдокод:<code> BuildKdTree(p_1, p_2P, Depth) //Input.A set of points P and the current depth Depth. //Output. ,p_n)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 <tex>P_1</tex> and <tex>P_2</tex> with a vertical line <tex>l</tex> {{through the median x-coordinate of the points in P else Split P into two subsets <tex>P_1</tex> and <tex>P_2</tex> with a horizontal line <tex>l</tex> through the median y-coordinate of the points in P. <tex>V_{left}</tex> <-BuildKdTree(<tex>P_1</tex>, Depth + 1) <tex>V_{right}} выпуклый многоугольник</tex> <- BuildKdTree(<tex>P_2</tex>, в котором порядок обхода вершин направлен против часовой стрелкиDepth + 1) Create a node v storing <tex>l</tex>, и никакие три последовательные точки не лежат на одной прямой. Найти пару чисел make <tex>\langle i, j \rangleV_{left}</tex>the left child of v, такие, что and make <tex>d(p_i, p_j)V_{right}</tex> максимальноthe right child of v. return v </code>

=== Опорные прямые ==={{ОпределениеЛемма|definitionabout=Прямая <tex>L</tex> называется '''опорной прямой''' (англ. ''line of support'') для многоугольника <tex>P</tex>, если его внутренность лежит по одну сторону от <tex>L</tex>, при этом <tex>L</tex> проходит хотя бы через одну из вершин <tex>P</tex>.}}{{ТеоремаО времени построения

Пусть <tex>L_1</tex> и <tex>L_2</tex> {{---}} две параллельные опорные прямые фигуры Построение выполняется за <tex>O(n \Phi</tex>, расстояние между которыми имеет максимальное значение. <tex>A_1</tex> и <tex>A_2</tex> {{---}} граничные точки фигуры <tex>\Phi</tex>, принадлежащие соответственно прямым <tex>L_1</tex> и <tex>L_2</tex>. Тогда отрезок <tex>A_1A_2</tex> перпендикулярен обеим прямым <tex>L_1</tex> и <tex>L_2log n)</tex>.

[[Файл:perpendicular.png|250px|right]]Предположим, что это не так. Тогда расстояние между прямыми Время построения обозначим <tex>L_1T(n)</tex> и <tex>L_2</tex> было бы меньше. Поиск медианы можно сделать за линейное время, чем отрезок <tex>A_1A_2</tex>поэтому достаточно очевидно, и тем более меньше, чем расстояние между двумя опорными прямыми что: <tex>L'_1T(n) = O(1)</tex> и if <tex>L'_2n = 1</tex> фигуры . <tex>T(n) = O(n) + 2 \Phicdot T(n / 2)</tex>, перпендикулярными к отрезку otherwise. Решением этого является <tex>A_1A_2T(n) = O(n \log n)</tex>. Также стоит отметить, что противоречит условиюможно и не искать медиану за линейное время, а просто посортить все точки в самом начале и дальше использовать это. В реализации попроще, асимптотика та же.

{{ТеоремаЛемма|about=О занимаемой памяти

Диаметр выпуклого многоугольника равен максимальному расстоянию между параллельными опорными прямымиK-d дерево требует <tex>O(n)</tex> памяти.

[[Файл:max_parallel.png|170px|right]]Пусть <tex>\Phi</tex> {{---}} выпуклая фигура, <tex>L_1</tex> и <tex>L_2</tex> {{---}} параллельные опорные прямые, расстояние между которыми имеет наибольшее возможное значение <tex>d</tex>, <tex>A_1</tex> и <tex>A_2</tex> {{---}} общие точки фигуры <tex>\Phi</tex> и прямых <tex>L_1</tex> и <tex>L_2</tex> соответственно. По предыдущей теореме <tex>A_1A_2</tex> перпендикулярен к прямым <tex>L_1</tex>Высота дерева, <tex>L_2</tex>очевидно, следовательно, его длина равна <tex>d</tex>. Докажем, что расстояние между любыми двумя точками фигуры <tex>\Phi</tex> не преводходит <tex>d</tex>. Действительно, если <tex>B</tex> и <tex>C</tex> {{---}} какие-либо две точки фигуры <tex>\Phi</tex>логарифмическая, а листьев всего <tex>m</tex> и <tex>O(n)</tex> {{---}} опорные прямые, перпендикулярные к отрезку <tex>BC</tex>, то отрезок <tex>BC</tex> не превосходит расстояния между прямыми <tex>m</tex> и . Поэтому будет <tex>O(n)</tex>вершин, которое в свою очередь не превосходит <tex>d</tex>. Следовательно, длина <tex>BC</tex> не может быть больше каждая занимает <tex>dO(1)</tex>памяти.

=== Алгоритм ===ЗаметимBy the way, что параллельные опорные прямые можно провести не через любую пару точекесли считать <tex>k</tex> константой, то и для случая большей размерности эти оценки будут такими же (доказывается аналогично).

{{Определение|definition== Запрос ==ТочкиПусть нам поступил какой-то прямоугольник <tex>R</tex>. Нужно вернуть все точки, через которые можно провести параллельные опорные прямыев нём лежат. Будем это делать рекурсивно, получая на вход корень дерева и сам прямоугольник <tex>R</tex>. Обозначим область, соответствующую вершине <tex>v</tex>, будем называть '''противолежащими''' как <tex>region(англv)</tex>. Она будет прямоугольником, одна или более границ которого могут быть на бесконечности. ''antipodal''<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>

[[Файл:calipers.png|250px|right]]Рассмотрим рисунок справа. Здесь <tex>LReportSubtree</tex> и <tex>M</tex> {{---}} опорные прямые, проходящие через вершины <tex>A</tex> и <tex>D</tex> соответственно. Значит, <tex>\langle A,D \rangle</tex> {{---}} противолежащая пара точек. Если начать вращать прямые против часовой стрелки вокруг данных точек, они будут оставаться опорными прямыми, пока одна из прямых не станет накладываться на сторону многоугольника. В нашем примере, при вращении <tex>M</tex> к позиции <tex>M'</tex>, <tex>M</tex> коснётся репортит все точки <tex>E</tex> раньше, чем <tex>L</tex> коснётся <tex>B</tex>, поэтому <tex>\langle A,E \rangle</tex> становится новой парой противолежащих точекв поддереве.

Теперь <tex>M'</tex> будет вращаться вокруг <tex>E</tex>By the way, точно так же можно перечислять точки в любом множестве, а <tex>L'</tex> продолжит вращаться вокруг <tex>A</tex>ведь нигде не используется, и следующей парой противолежащих точек станет что <tex>\langle B,E \rangleR</tex>. Продолжая таким образом, мы сгенерируем все пары противолежащих точек, так как параллельные линии пройдут под всеми возможными углами. Определение новой пары противолежащих точек требует только одного сравнения углов, которое можно выполнить с помощью предиката поворота{{---}} прямоугольник.

Представленный выше алгоритм генерирует все пары противолежащих Перечисление точек в многоугольнике прямоугольнике выполняется за <tex>P</tex>, состоящем из <tex>NO(\sqrt n + ans)</tex> вершин, за время где <tex>O(N)ans</tex>{{---}} размер ответа.

Данный алгоритм можно реализовать следующим образом: хранить указатели на противолежащие вершиныСперва заметим, что все <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>Q(n) = O(\sqrt n)</tex> является решением. Таким образомПринимая во внимание всё, что писалось выше, каждая из вершин будет посещена каждой из прямых не более двух разполучаем требуемое.