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

19

O algoritmo de Ramer-Douglas-Peucker para simplificação de linha possui o pior tempo de execução de O(n2) . Para entradas aleatórias distribuídas adequadamente, espera-se complexidade do tempo de execução de O(nlogn) . Em 2D, existem outros algoritmos com pior complexidade de tempo de execução O(nlogn) , 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(nlogn) (independente da entrada) para o caso de linhas 4D? Você pode assumir distâncias euclidianas e uma tolerância absoluta global.

Thomas Klimpel
fonte

Respostas:

0

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.PRdϵ0ϵPκF(ϵ/2,P)O(nlogn)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.


O(nlogn)

Mal
fonte