64
правки
Изменения
Новая страница: «{{В разработке}} Есть множество точек на плоскости. Нужно найти две самые удалённые из них...»
{{В разработке}}
Есть множество точек на плоскости. Нужно найти две самые удалённые из них.
Найдём выпуклую оболочку исходного множества и получим более простую задачу: найти две наиболее удалённые вершины в выпуклом многоугольнике. Сделать это можно за линейное время с помощью метода, который называется '''вращающиеся калиперы''' (англ. ''rotating calipers'').
== Постановка задачи ==
Пусть <tex>P = (p_1, p_2, ... ,p_n)</tex> {{---}} выпуклый многоугольник, в котором порядок обхода вершин направлен против часовой стрелки, и никакие три последовательные точки не лежат на одной прямой. Найти пару чисел <tex>\langle i, j \rangle</tex>, такие, что <tex>d(p_i, p_j)</tex> максимально.
== Вращающиеся калиперы ==
{{Определение
|definition=
Прямая <tex>L</tex> называется '''опорной прямой''' (англ. ''line of support'') для многоугольника <tex>P</tex>, если его внутренность лежит по одну сторону от <tex>L</tex>, при этом <tex>L</tex> проходит хотя бы через одну из вершин <tex>P</tex>.
}}
{| border=0 width="100%"
|{{Лемма
|statement=
Пусть <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=
Предположим, что это не так. Тогда расстояние между прямыми <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]]
|}
Так как <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>\Phi</tex>.
{{Лемма
|statement=
Диаметр выпуклого полигона равен максимальному расстоянию между параллельными опорными прямыми.
|proof=
}}
[[Категория: Вычислительная геометрия]]
Есть множество точек на плоскости. Нужно найти две самые удалённые из них.
Найдём выпуклую оболочку исходного множества и получим более простую задачу: найти две наиболее удалённые вершины в выпуклом многоугольнике. Сделать это можно за линейное время с помощью метода, который называется '''вращающиеся калиперы''' (англ. ''rotating calipers'').
== Постановка задачи ==
Пусть <tex>P = (p_1, p_2, ... ,p_n)</tex> {{---}} выпуклый многоугольник, в котором порядок обхода вершин направлен против часовой стрелки, и никакие три последовательные точки не лежат на одной прямой. Найти пару чисел <tex>\langle i, j \rangle</tex>, такие, что <tex>d(p_i, p_j)</tex> максимально.
== Вращающиеся калиперы ==
{{Определение
|definition=
Прямая <tex>L</tex> называется '''опорной прямой''' (англ. ''line of support'') для многоугольника <tex>P</tex>, если его внутренность лежит по одну сторону от <tex>L</tex>, при этом <tex>L</tex> проходит хотя бы через одну из вершин <tex>P</tex>.
}}
{| border=0 width="100%"
|{{Лемма
|statement=
Пусть <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=
Предположим, что это не так. Тогда расстояние между прямыми <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]]
|}
Так как <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>\Phi</tex>.
{{Лемма
|statement=
Диаметр выпуклого полигона равен максимальному расстоянию между параллельными опорными прямыми.
|proof=
}}
[[Категория: Вычислительная геометрия]]
