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

Эта статья находится в разработке!

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

Найдём выпуклую оболочку исходного множества и получим более простую задачу: найти две наиболее удалённые вершины в выпуклом многоугольнике. Сделать это можно за линейное время с помощью метода, который называется вращающиеся калиперы (англ. 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]

Литература

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