1632
правки
Изменения
м
{{В разработке}}
rollbackEdits.php mass rollback
Есть множество точек на плоскости. Нужно найти две самые удалённые из них.
[[Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull|Найдём выпуклую оболочку]] исходного множества и получим более простую задачу: найти две наиболее удалённые вершины в выпуклом многоугольнике. Сделать это можно за линейное время с помощью метода, который называется '''вращающиеся калиперы''' (англ. ''rotating calipers'').
''Обоснование: Пусть диаметр с одной стороны содержит точку, которая не принадлежит выпуклой оболочке. Тогда продлим диаметр в эту сторону до пересечения с выпуклой оболочкой. Очевидно, он станет длиннее. А потом заметим, что диаметр станет еще больше, если сдвинуть его к одному из концов ребра, в которое мы уперлись. Конец.''
== Постановка задачи ==
|[[Файл:calipers.png|250px|thumb|right]]
|}
=== Асимптотика ===
{{Теорема
|statement=
Представленный выше алгоритм генерирует все пары противолежащих точек в многоугольнике <tex>P</tex>, состоящем из <tex>N</tex> вершин, за время <tex>O(N)</tex>.
|proof=
Данный алгоритм можно реализовать следующим образом: хранить указатели на противолежащие вершины, и на каждой итерации алгоритма увеличивать либо один из данных указателей, либо сразу оба (когда обе прямые проходят через сторону многоугольника), и заканчивать работу, когда опорные прямые сделают полный круг. Таким образом, каждая из вершин будет посещена каждой из прямых не более двух раз.
}}
== Ссылки ==
