Строка, которая запускает наихудший случай для алгоритма Дугласа-Пекера?

алгоритм упрощения линии Дугласа-Пекера имеет временная сложность O(n²) в наихудшем случае. Однако для того, чтобы линия действительно вызвала этот наихудший случай, две вещи должны пойти «не так» одновременно:

  • порог должен быть установлен настолько низким, чтобы сохранялось большинство вершин
  • на каждом шаге рекурсии вершина с наибольшим отклонением от линии между текущими конечными точками должна быть близка (с точки зрения ее индекса на линии, а не с точки зрения ее евклидовой позиции) к одной из конечные точки. (Если вместо этого индекс вершины с наибольшим отклонением от линии был достаточно близок к середине между текущими конечными точками, алгоритм должен вызывать рекурсивное двоичное подразделение глубины log(n), что приводит к общей временной сложности O(n log(n)).)

В то время как первый критерий легко активировать (просто установите порог допуска на 0,0), я еще не нашел строку, удовлетворяющую второму критерию.

Итак, есть ли простой пример строки, который приводит к наихудшему поведению (предпочтительно тот, который запускает очевидный наихудший случай, когда точка с наибольшим отклонением на каждом шаге рекурсии напрямую связана с одной из конечных точек линии; но любой другой пример тоже нормально)?


recursion algorithm time-complexity douglas-peucker
person Dreamer    schedule 20.07.2015    source источник
comment
Подойдет какой-нибудь «зигзаг». Например, рассмотрим некоторые точки с позициями x [0, 1, ..., 10] и y-позициями [0, 10, -9, 8, ..., 0]. Когда рисуешь, это легче увидеть ;)   -  person Vincent van der Weele    schedule 20.07.2015

Ответы (1)


arrow_upward
5
arrow_downward

Таким образом, Винсент ван дер Вил кажется правым, простая зигзагообразная линия с увеличивающейся амплитудой вызовет наихудший случай O(n²) для алгоритма Дугласа-Пекера:

введите здесь описание изображения

В этом случае вершина с наибольшим расстоянием от линии, соединяющей две конечные точки, всегда будет вершиной, непосредственно примыкающей к конечной точке справа. Таким образом, алгоритм Дугласа-Пекера здесь потребует O(n) шагов подразделения, где каждый шаг просто бреет крайнюю правую вершину и, таким образом, необходимо выполнить итерацию по оставшимся O(n) вершинам, чтобы найти вершину с наибольшим расстоянием, что дает общая временная сложность O (n²)

person Dreamer    schedule 22.07.2015