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