170
правок
Изменения
м
{{В разработке}}
Нет описания правки
Есть множество точек на плоскости. Нужно найти две самые удалённые из них.
[[Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull|Найдём выпуклую оболочку]] исходного множества и получим более простую задачу: найти две наиболее удалённые вершины в выпуклом многоугольнике. Сделать это можно за линейное время с помощью метода, который называется '''вращающиеся калиперы''' (англ. ''rotating calipers'').
''Обоснование: Пусть диаметр с одной стороны содержит точку, которая не принадлежит выпуклой оболочке. Тогда продлим диаметр в эту сторону до пересечения с выпуклой оболочкой. Очевидно, он станет длиннее. А потом заметим, что диаметр станет еще больше, если сдвинуть его к одному из концов ребра, в которое мы уперлись. Конец.''
== Постановка задачи ==
{{Определение
|definition=
Точки, через которые можно провести параллельные опорные прямые, будем называть '''противоположнымипротиволежащими''' (англ. ''antipodal'').
}}
Благодаря предыдущей теореме нам нужно рассмотреть только противоположные противолежащие точки. Задача в том, чтобы рассмотреть их, не перебирая все пары точек.
{|border="0" width="100%"
|Рассмотрим рисунок справа. <tex>L</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>, а <tex>L'</tex> продолжит вращаться вокруг <tex>A</tex>, и следующей парой противоположных противолежащих точек станет <tex>\langle B,E \rangle</tex>. Продолжая таким образом, мы сгенерируем все пары противоположных противолежащих точек, так как параллельные линии пройдут под всеми возможными углами. Определение новой пары противоположных противолежащих точек требует только одного сравнения углов, которое можно выполнить с помощью предиката поворота.
|[[Файл:calipers.png|250px|thumb|right]]
|}
=== Асимптотика ===
{{Теорема
|statement=
Представленный выше алгоритм генерирует все пары противолежащих точек в многоугольнике <tex>P</tex>, состоящем из <tex>N</tex> вершин, за время <tex>O(N)</tex>.
|proof=
Данный алгоритм можно реализовать следующим образом: хранить указатели на противолежащие вершины, и на каждой итерации алгоритма увеличивать либо один из данных указателей, либо сразу оба (когда обе прямые проходят через сторону многоугольника), и заканчивать работу, когда опорные прямые сделают полный круг. Таким образом, каждая из вершин будет посещена каждой из прямых не более двух раз.
}}
== Ссылки ==
