64
правки
Изменения
Нет описания правки
|[[Файл:calipers.png|250px|thumb|right]]
|}
=== Асимптотика ===
{{Теорема
|statement=
Представленный выше алгоритм генерирует все пары противолежащих точек в многоугольнике <tex>P</tex>, состоящем из <tex>N</tex> вершин за время <tex>O(N)</tex>.
|proof=
Данный алгоритм можно реализовать следующим образом: хранить указатели на противолежащие вершины и на каждой итерации алгоритма увеличивать либо один из данных указателей, либо сразу оба (когда обе прямые проходят через сторону многоугольника), и заканчивать работу, когда опорные прямые сделают полный круг. Таким образом, каждая из вершин будет посещена каждой из прямых не более двух раз.
}}
== Ссылки ==
