¿Existe un algoritmo O (n log n) para la simplificación de línea 4D?

19

El algoritmo Ramer-Douglas-Peucker para la simplificación de línea tiene el peor tiempo de ejecución . Para entradas aleatorias distribuidas adecuadamente, se espera una complejidad de tiempo de ejecución . En 2D, hay otros algoritmos con la peor complejidad de tiempo de ejecución , que calculan exactamente el mismo resultado que el algoritmo Ramer-Douglas-Peucker. Dado que estos algoritmos se basan en una estructura de datos de "ruta (casco convexo)", no es obvio si pueden generalizarse a líneas 4D.O(n2)O(nlogn)O(nlogn)

¿Existe un algoritmo (aleatorio) que tenga (esperado) tiempo de ejecución (independiente de la entrada) para el caso de líneas 4D? Puede asumir distancias euclidianas y una tolerancia absoluta global.O(nlogn)

Thomas Klimpel
fuente

Respuestas:

0

El algoritmo que funciona con el caso 4D se describe en el artículo Algoritmos de aproximación de tiempo casi lineal para la simplificación de curvas por cuatro autores: Pankaj K. Agarwal, Sariel Har-Peled, Nabil H. Mustafa y Yusu Wang .

Dada una curva poligonal en y un parámetro , se puede construir una -simplificación de con un tamaño máximo de en tiempo y espacio.PRdϵ0ϵPκF(ϵ/2,P)O(nlogn)O(n)

El algoritmo no depende de las propiedades de monotonicidad. Cubre la línea original con discos y busca el recorrido de la línea en el conjunto ordenado.


Nota al margen : hay una modificación del algoritmo de Douglas-Peucker con el peor de los casos en descrito en el artículo An O (n log n) Implementation of the Douglas-Peucker Algorithm for Line Simplification. por John Hershberger y Jack Snoeyink : simplificación mejorada de la línea DP . De hecho, utiliza el casco del camino.O(nlogn)

Mal
fuente