304
правки
Изменения
Нет описания правки
<br clear="all"/>
===Решение альтернативной задачи===
Альтернативную задачу с заданным числом <tex>k</tex> оптимально решать так, что в итоговой цепи останутся лишь наиболее значимые точки. Алгоритм начинается как и для обычной задачи. Теперь каждый раз выберается ту часть, у которой наиболее удаленная вершина находится на большем расстоянии относительно всех остальных. Алгоритм завершится, когда будет итоговая цепь будет состоять из требуемого числа точек. ====Реализация====Практически очевидно, что данный вариант алгоритма легко реализовать на приоритетной очереди. Будем хранить расстояние, на котором находится наиболее удаленная вершина, как ключ, а номера вершин-границ как значение. На каждой итерации мы выбираем обьект с наибольшим ключем, делим и получившиеся части кладем обратно в очередь с новыми ключами.
==Обзор ускорения работы алгоритма Дугласа-Пекера==
Как описано выше, в худшем случае алгоритм работает за <tex>O(n^2)</tex>. Можно внести дополнения, которые позволят получить <tex>O(n\log n)</tex> в худшем случае. Ускорение основывается на уменьшении времени поиска наиболее удаленной вершины. Это можно осуществить благодаря идее о том, что наиболее удаленная вершина лежит на выпуклой оболочке полигональной цепи.
