Существует ли алгоритм O (n log n) для упрощения четырехмерной линии?

19

Алгоритм Рамер-Дуглас-Peucker для упрощения линии имеет наихудший среда выполнения. Для правильно распределенных случайных входов ожидаемая сложность времени выполнения . В 2D есть другие алгоритмы со сложностью времени выполнения худшем случае , которые вычисляют точно такой же результат, что и алгоритм Рамера-Дугласа-Пекера. Поскольку эти алгоритмы основаны на структуре данных «траектория (выпуклая) оболочка», неясно, могут ли они быть обобщены до четырехмерных линий.О(N2)О(NжурналN)О(NжурналN)

Существует ли (рандомизированный) алгоритм, который имеет (ожидаемое) время выполнения (независимо от ввода) для случая четырехмерных линий? Вы можете принять евклидовы расстояния и глобальную абсолютную терпимость.О(NжурналN)

Томас Климпел
источник

Ответы:

0

Алгоритм, работающий с 4D случаем, описан в статье Алгоритмы аппроксимации ближнего времени для упрощения кривых четырьмя авторами: Панкаджем К. Агарвалом, Сариэлем Хар-Пеледом, Набилем Х. Мустафой и Юсу Вангом .

Учитывая ломаная в R d и параметр & epsi ; 0 , & epsi ; -simplification из Р с размером не более κ F ( & epsi ; / 2 , Р ) может быть построена в O ( п войти п ) времени и O ( п ) Космос.прdε0εпκF(ε/2,п)О(NжурналN)О(N)

Алгоритм не зависит от свойств монотонности. Он покрывает исходную строку дисками и ищет обход строки в упорядоченном множестве.


О(NжурналN)

Зло
источник