Диаметр множества точек (вращающиеся калиперы)

НЕТ ВОЙНЕ

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

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

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

Есть множество точек на плоскости. Нужно найти две самые удалённые из них.

Найдём выпуклую оболочку исходного множества и получим более простую задачу: найти две наиболее удалённые вершины в выпуклом многоугольнике. Сделать это можно за линейное время с помощью метода, который называется вращающиеся калиперы (англ. rotating calipers).

Обоснование: Пусть диаметр с одной стороны содержит точку, которая не принадлежит выпуклой оболочке. Тогда продлим диаметр в эту сторону до пересечения с выпуклой оболочкой. Очевидно, он станет длиннее. А потом заметим, что диаметр станет еще больше, если сдвинуть его к одному из концов ребра, в которое мы уперлись. Конец.

Постановка задачи

Пусть [math]P = (p_1, p_2, ... ,p_n)[/math] — выпуклый многоугольник, в котором порядок обхода вершин направлен против часовой стрелки, и никакие три последовательные точки не лежат на одной прямой. Найти пару чисел [math]\langle i, j \rangle[/math], такие, что [math]d(p_i, p_j)[/math] максимально.

Вращающиеся калиперы

Опорные прямые

Определение:

Прямая [math]L[/math] называется опорной прямой (англ. line of support) для многоугольника [math]P[/math], если его внутренность лежит по одну сторону от [math]L[/math], при этом [math]L[/math] проходит хотя бы через одну из вершин [math]P[/math].

Теорема: Пусть [math]L_1[/math] и [math]L_2[/math] — две параллельные опорные прямые фигуры [math]\Phi[/math], расстояние между которыми имеет максимальное значение. [math]A_1[/math] и [math]A_2[/math] — граничные точки фигуры [math]\Phi[/math], принадлежащие соответственно прямым [math]L_1[/math] и [math]L_2[/math]. Тогда отрезок [math]A_1A_2[/math] перпендикулярен обеим прямым [math]L_1[/math] и [math]L_2[/math]. Доказательство: [math]\triangleright[/math] Предположим, что это не так. Тогда расстояние между прямыми [math]L_1[/math] и [math]L_2[/math] было бы меньше, чем отрезок [math]A_1A_2[/math], и тем более меньше, чем расстояние между двумя опорными прямыми [math]L'_1[/math] и [math]L'_2[/math] фигуры [math]\Phi[/math], перпендикулярными к отрезку [math]A_1A_2[/math], что противоречит условию. [math]\triangleleft[/math]

Так как [math]A_1[/math] и [math]A_2[/math] — какие угодно граничные точки фигуры [math]\Phi[/math], принадлежащие соответственно прямым [math]L_1[/math] и [math]L_2[/math], то из перпендикулярности отрезка [math]A_1A_2[/math] к прямым [math]L_1[/math] и [math]L_2[/math] следует, что ни одна из прямых [math]L_1[/math], [math]L_2[/math] не может иметь с фигурой [math]\Phi[/math] целый общий отрезок. Другими словами, каждая из этих прямых содержит единственную граничную точку фигуры [math]\Phi[/math].

Теорема: Диаметр выпуклого многоугольника равен максимальному расстоянию между параллельными опорными прямыми. Доказательство: [math]\triangleright[/math] Пусть [math]\Phi[/math] — выпуклая фигура, [math]L_1[/math] и [math]L_2[/math] — параллельные опорные прямые, расстояние между которыми имеет наибольшее возможное значение [math]d[/math], [math]A_1[/math] и [math]A_2[/math] — общие точки фигуры [math]\Phi[/math] и прямых [math]L_1[/math] и [math]L_2[/math] соответственно. По предыдущей теореме [math]A_1A_2[/math] перпендикулярен к прямым [math]L_1[/math], [math]L_2[/math], следовательно, его длина равна [math]d[/math]. Докажем, что расстояние между любыми двумя точками фигуры [math]\Phi[/math] не преводходит [math]d[/math]. Действительно, если [math]B[/math] и [math]C[/math] — какие-либо две точки фигуры [math]\Phi[/math], а [math]m[/math] и [math]n[/math] — опорные прямые, перпендикулярные к отрезку [math]BC[/math], то отрезок [math]BC[/math] не превосходит расстояния между прямыми [math]m[/math] и [math]n[/math], которое в свою очередь не превосходит [math]d[/math]. Следовательно, длина [math]BC[/math] не может быть больше [math]d[/math]. [math]\triangleleft[/math]

Алгоритм

Заметим, что параллельные опорные прямые можно провести не через любую пару точек.

Определение:

Точки, через которые можно провести параллельные опорные прямые, будем называть противолежащими (англ. antipodal).

Благодаря предыдущей теореме нам нужно рассмотреть только противолежащие точки. Задача в том, чтобы рассмотреть их, не перебирая все пары точек.

Рассмотрим рисунок справа. [math]L[/math] и [math]M[/math] — опорные прямые, проходящие через вершины [math]A[/math] и [math]D[/math] соответственно. Значит, [math]\langle A,D \rangle[/math] — противолежащая пара точек. Если начать вращать прямые против часовой стрелки вокруг данных точек, они будут оставаться опорными прямыми, пока одна из прямых не станет накладываться на сторону многоугольника. В нашем примере, при вращении [math]M[/math] к позиции [math]M'[/math], [math]M[/math] коснётся точки [math]E[/math] раньше, чем [math]L[/math] коснётся [math]B[/math], поэтому [math]\langle A,E \rangle[/math] становится новой парой противолежащих точек. Теперь [math]M'[/math] будет вращаться вокруг [math]E[/math], а [math]L'[/math] продолжит вращаться вокруг [math]A[/math], и следующей парой противолежащих точек станет [math]\langle B,E \rangle[/math]. Продолжая таким образом, мы сгенерируем все пары противолежащих точек, так как параллельные линии пройдут под всеми возможными углами. Определение новой пары противолежащих точек требует только одного сравнения углов, которое можно выполнить с помощью предиката поворота.

Асимптотика

Теорема:

Представленный выше алгоритм генерирует все пары противолежащих точек в многоугольнике [math]P[/math], состоящем из [math]N[/math] вершин, за время [math]O(N)[/math].

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

[math]\triangleright[/math]

Данный алгоритм можно реализовать следующим образом: хранить указатели на противолежащие вершины, и на каждой итерации алгоритма увеличивать либо один из данных указателей, либо сразу оба (когда обе прямые проходят через сторону многоугольника), и заканчивать работу, когда опорные прямые сделают полный круг. Таким образом, каждая из вершин будет посещена каждой из прямых не более двух раз.

[math]\triangleleft[/math]

Ссылки

• M.I. Shamos Computational geometry, 1978 — С. 76.
• Яглом И.М., Болтянский В.Г. Выпуклые фигуры, 1951 — С. 20, 144.
• Реализация - Github.com