Existe um algoritmo O (n log n) para simplificação da linha 4D?

O algoritmo de Ramer-Douglas-Peucker para simplificação de linha possui o pior tempo de execução de $O(n^2)$ . Para entradas aleatórias distribuídas adequadamente, espera-se complexidade do tempo de execução de $O(n \log n)$ . Em 2D, existem outros algoritmos com pior complexidade de tempo de execução $O(n \log n)$ , que calculam exatamente o mesmo resultado que o algoritmo de Ramer-Douglas-Peucker. Como esses algoritmos são baseados em uma estrutura de dados de "caminho (convexo)", não é óbvio se eles podem ser generalizados em linhas 4D.

Existe um algoritmo (randomizado) que tenha (esperado ) tempo de execução $O(n \log n)$ (independente da entrada) para o caso de linhas 4D? Você pode assumir distâncias euclidianas e uma tolerância absoluta global.

O algoritmo que trabalha com o caso 4D é descrito no artigo Algoritmos de aproximação de tempo quase linear para simplificação de curvas por quatro autores: Pankaj K. Agarwal, Sariel Har-Peled, Nabil H. Mustafa e Yusu Wang .

Dada uma curva poligonal em R d e um parâmetro ε ≥ 0 , um ε -simplification de P com tamanho de no máximo κ F ( ε / 2 , P ) pode ser construído em O ( N log N ) tempo e S ( n ) espaço.$P$$\mathcal R^d$$\epsilon \ge 0$$\epsilon$$P$$\mathcal \kappa_F(\epsilon/2, P)$$\mathcal O(n\log n)$$\mathcal O(n)$

O algoritmo não depende das propriedades de monotonicidade. Ele cobre a linha original com discos e procura a passagem da linha no conjunto solicitado.

$\mathcal O(n\log n)$