Hay que tener en cuenta algunas cosas. El método de Newton también se equivocará a veces. Tendrás puntos en el tiempo en los que la distancia más cercana no está en ninguna raíz. Que al calcular las raíces y comprobarlas te dará una respuesta errónea. Y no hay nada que puedas hacer al respecto.
El método de discretización ingenuo va a ser $n^2$ tiempo con lo cerca que quieres los valores, y se va a empantanar o estar más equivocado. Pero se puede mejorar mucho esto. Yo sugeriría fuertemente la resolución variable para ese método, donde usted encuentra el punto más cercano en los dos gráficos sobre los valores k-discretos. Entonces, si encuentras que, por ejemplo, los valores en 43 y 22 son los más cercanos, haces lo mismo que acabas de hacer pero dentro del rango de 42-44 y 21-23 dentro de los dos gráficos en lugar de para todo el gráfico. Así que si quieres precisión en la 10.000ª parte del gráfico, no realizas 100.000.000 de comprobaciones de distancia, sino 50.000 comprobaciones de distancia, subdividiendo el gráfico en 100 partes, encontrando los rangos alrededor de esos puntos más cercanos en 200 puntos de distancias diferentes. Obviamente, también puedes acelerar esto conociendo el orden de los gráficos y sabiendo que no puede acercarse espontáneamente más veces de las que tiene las raíces a través del teorema de Bezout. O cualquiera de las otras formas de encontrar el punto más cercano a una curva de Bézier (que es un problema mucho más fácil).
En cuanto a la informática, creo que claramente el mejor método es hacer una subdivisión en forma de bézier de ambas curvas, encontrando los recuadros delimitadores más cercanos entre sí, mientras se deja de comprobar inteligentemente aquellos recuadros delimitadores que se pueden descartar abiertamente. Es decir, si la parte más cercana del cuadro delimitador está más lejos que los elementos más lejanos del par de cuadros delimitadores conocidos más cercanos, entonces no es posible que toda esa parte del gráfico contenga la distancia más corta, si alegamos ignorancia total entonces el gráfico podría estar en cualquier parte de un cuadro delimitador. Una vez que dividimos el gráfico unas cuantas veces, habría una amplia resolución que nos permitiría mostrar fácilmente ejemplos en los que incluso el mejor escenario entre un emparejamiento es peor que el peor escenario de otro emparejamiento. Así, sabemos que ese emparejamiento no puede tener el punto más cercano. Además, si podemos demostrar que esto es cierto entre algún cuadro delimitador de un gráfico y todos los cuadros delimitadores del otro gráfico, se demuestra que toda la sección del gráfico es inválida.
Este método convergería realmente con bastante rapidez, ya que podríamos deshacernos rápidamente de secciones enteras del gráfico o, en el caso de muchos gráficos, de gráficos enteros, incluso sin necesidad de comprobarlos más allá de una comprobación de cajas delimitadoras. En el caso de que los dos gráficos tengan una intersección, las cajas delimitadoras superpuestas se someterían rápidamente a divisiones repetidas y a encontrar en el peor de los casos una distancia de cero o épsilon. Y, por lo tanto, desestimar todo el resto del gráfico a menos que exista otra intersección.
Esto también se combinaría fácilmente con un montón de trucos muy agradables y, en última instancia, inteligentes que se pueden hacer para determinar las distancias y el solapamiento dentro de las cajas delimitadoras alineadas con el eje (AABB) de la geometría computacional. Si bien es cierto que el gráfico de una curva de Bézier se encuentra categóricamente dentro del polígono del casco convexo definido por los puntos, y la caja delimitadora contiene más área, es más fácil y probablemente mejor computacionalmente obtener sólo la caja delimitadora de la curva. Sobre todo si tenemos en cuenta una serie de grandes trucos que nos permiten localizar el rectángulo más cercano en menos de $n$ tiempo. Si este tipo de cosas son de misión crítica, sin duda se podrían realizar suficientes trucos para encontrar todas las respuestas correctas más cerca de algún nivel arbitrario de error en periodos de tiempo imperceptiblemente cortos.
