304
правки
Изменения
Нет описания правки
==Обзор алгоритмов сохраняющих топологию==
В статье де Берга (de Berg) A New Approach to Subdivision Simplification приведен алгоритм, позволяющий решающий чуть более общую задачу чем наша, упрощение полигональной цепи с учетом обязательных особых точек не входящих в нее. Мы можем использовать алгоритм и для нашего случая задав множество особых точек пустый. Время работы алгоритма для нашего случая составит <tex>O\left(n^2\log n\right)</tex>.
==Ссылки==
*[http://softsurfer.com/Archive/algorithm_0203/algorithm_0203.htm Алгоритм Мелкмана]
*[http://softsurfer.com/Archive/algorithm_0112/algorithm_0112.htm Двоичный поиск на выпуклой оболочке]
*[http://www.bowdoin.edu/~ltoma/teaching/cs350/spring06/Lecture-Handouts/deberg95new.pdf A New Approach to Subdivision Simplification]
