64
правки
Изменения
Нет описания правки
}}
{| 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>.
{| border="0" width="100%"
|{{ЛеммаТеорема
|statement=
Диаметр выпуклого многоугольника равен максимальному расстоянию между параллельными опорными прямыми.
|proof=
Пусть <tex>\Phi</tex> {{---}} выпуклая фигура, <tex>L_1</tex> и <tex>L_2</tex> {{---}} параллельные опорные прямые, расстояние между которыми имеет наибольшее возможное значение <tex>d</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>d</tex>. Докажем, что расстояние между любыми двумя точками фигуры <tex>\Phi</tex> не преводходит <tex>d</tex>. Действительно, если <tex>B</tex> и <tex>C</tex> {{---}} какие-либо две точки фигуры <tex>\Phi</tex>, а <tex>m</tex> и <tex>n</tex> {{---}} опорные прямые, перпендикулярные к отрезку <tex>BC</tex>, то отрезок <tex>BC</tex> не превосходит расстояния между прямыми <tex>m</tex> и <tex>n</tex>, которое в свою очередь не превосходит <tex>d</tex>. Следовательно, длина <tex>BC</tex> не может быть больше <tex>d</tex>.
}}
|[[Файл:max_parallel.png|170px|thumb|right]]
|}
Заметим, что параллельные опорные прямые можно провести не через любую пару точек.
{{Определение
|definition=
Точки, через которые можно провести параллельные опорные прямые, будем называть '''противоположными''' (англ. ''antipodal'').
}}
Благодаря предыдущей теореме нам нужно рассмотреть только противоположные точки. Задача в том, чтобы рассмотреть их, не перебирая все пары точек.
{|border="0" width="100%"
|Рассмотрим рисунок справа. <tex>L</tex> и <tex>M</tex> {{---}} опорные прямые, проходящие через вершины <tex>A</tex> и <tex>D</tex> соответственно. Значит, <tex>\langle A,D \rangle</tex> {{---}} противоположная пара точек. Если начать вращать прямые против часовой стрелки вокруг данных точек, они будут оставаться опорными прямыми, пока одна из прямых не станет накладываться на сторону многоугольника. В нашем примере, при вращении <tex>M</tex> к позиции <tex>M'</tex>, <tex>M</tex> коснётся точки <tex>E</tex> раньше, чем <tex>L</tex> коснётся <tex>B</tex>, поэтому <tex>\langle A,E \rangle</tex> становится новой парой противоположных точек.
Теперь <tex>M'</tex> будет вращаться вокруг <tex>E</tex>, а <tex>L'</tex> продолжит вращаться вокруг <tex>A</tex>, и следующей парой противоположных точек станет <tex>\langle B,E \rangle</tex>. Продолжая таким образом, мы сгенерируем все пары противоположных точек, так как параллельные линии пройдут под всеми возможными углами. Определение новой пары противоположных точек требует только одного сравнения углов, которое можно выполнить с помощью предиката поворота.
|[[Файл:calipers.png|250px|thumb|right]]
|}
== Литература ==
* ''M.I. Shamos'' Computational geometry, 1978 {{---}} С. 76.
