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