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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{В разработке}} Есть множество точек на плоскости. Нужно найти две самые удалённые из них...»)
 
Строка 18: Строка 18:
 
Пусть <tex>L_1</tex> и <tex>L_2</tex> {{---}} две параллельные опорные прямые фигуры <tex>\Phi</tex>, расстояние между которыми имеет максимальное значение. <tex>A_1</tex> и <tex>A_2</tex> {{---}} граничные точки фигуры <tex>\Phi</tex>, принадлежащие соответственно прямым <tex>L_1</tex> и <tex>L_2</tex>. Тогда отрезок <tex>A_1A_2</tex> перпендикулярен обеим прямым <tex>L_1</tex> и <tex>L_2</tex>.
 
Пусть <tex>L_1</tex> и <tex>L_2</tex> {{---}} две параллельные опорные прямые фигуры <tex>\Phi</tex>, расстояние между которыми имеет максимальное значение. <tex>A_1</tex> и <tex>A_2</tex> {{---}} граничные точки фигуры <tex>\Phi</tex>, принадлежащие соответственно прямым <tex>L_1</tex> и <tex>L_2</tex>. Тогда отрезок <tex>A_1A_2</tex> перпендикулярен обеим прямым <tex>L_1</tex> и <tex>L_2</tex>.
 
|proof=
 
|proof=
Предположим, что это не так. Тогда расстояние между прямыми <tex>L_1</tex> и <tex>L_2</tex> было бы меньше, чем отрезок <tex>A_1A_2</tex>, и тем более менше, чем расстояние между двумя опорными прямыми <tex>L'_1</tex> и <tex>L'_2</tex> фигуры <tex>\Phi</tex>, перпендикулярными к отрезку <tex>A_1A_2</tex>, что противоречит условию.
+
Предположим, что это не так. Тогда расстояние между прямыми <tex>L_1</tex> и <tex>L_2</tex> было бы меньше, чем отрезок <tex>A_1A_2</tex>, и тем более меньше, чем расстояние между двумя опорными прямыми <tex>L'_1</tex> и <tex>L'_2</tex> фигуры <tex>\Phi</tex>, перпендикулярными к отрезку <tex>A_1A_2</tex>, что противоречит условию.
 
}}
 
}}
 
|[[Файл:perpendicular.png|250px|thumb|right]]
 
|[[Файл:perpendicular.png|250px|thumb|right]]
Строка 31: Строка 31:
  
 
}}
 
}}
 +
 +
== Литература ==
 +
* ''M.I. Shamos'' Computational geometry, 1978 {{---}} С. 76.
 +
* ''Яглом И.М., Болтянский В.Г.'' Выпуклые фигуры, 1951 {{---}} С. 20, 144.
  
 
[[Категория: Вычислительная геометрия]]
 
[[Категория: Вычислительная геометрия]]

Версия 04:35, 8 января 2014

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

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

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

Так как [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].

Лемма:
Диаметр выпуклого полигона равен максимальному расстоянию между параллельными опорными прямыми.

Литература

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