Изменения
→Топология
К сожалению, алгоритм Дугласа-Пекера в ходе своей работы не сохраняет топологию. Это означает, что в ответе мы можем получить линию с самопересечениями.
В статье де Берга (de Berg) ''A New Approach to Subdivision Simplification'' приведен алгоритм, позволяющий решать чуть более общую задачу, чем текущая: упрощение полигональной цепи с учетом обязательных особых точек, не входящих в нее и с учетом топологии. Можно использовать алгоритм и для текущего случая, задав множество особых точек пустым. Время работы алгоритма при этом составит <tex>O(n^2\log n)</tex>. Краткое описание алгоритма дано ниже.
====Оптимальность====
