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