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.
¿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.
fuente