Planteamiento del problema: Dados dos puntos $a$ y $b$ en el espacio 3D y una trayectoria/curva arbitraria $S$ (de longitud conocida $L(S)$ ) entre los dos puntos, hallar un límite superior ajustado para la distancia (euclídea) del punto medio entre $a$ y $b$ , llámalo punto $c$ y cualquier punto $Sp$ en la curva $S$ .
Por lo tanto, si la distancia euclidiana entre $c$ y $Sp$ es $D(c,Sp)$ y $F(L(S))$ es función de la longitud del trayecto $L(S)$ ,
encontrar $F(L(S))$ tal que para cada $Sp$ que pertenece a $S$
$D(c,Sp) \leq F(L(S))$
Por ejemplo, un límite superior que he encontrado es $$D(c, Sp) \leq \frac{L(s)+l}{2}$$ donde $l$ es la distancia euclidiana entre los puntos $a$ y $b$ (los puntos finales de la curva $S$ ).
Esto es bastante sencillo de demostrar. Supongamos que el punto de la curva más alejado (en línea recta) del punto $c$ . Entonces como $l/2$ es la distancia a recorrer desde $c$ a $a$ o $b$ y $L(s)/2$ es la distancia máxima que hay que recorrer a lo largo de la curva $S$ para llegar a cualquiera de sus puntos (dado que se puede ir allí desde cualquiera de los dos $a$ o $b$ ) entonces la distancia en línea recta del punto de la curva más alejado de $c$ será igual o menor que eso.
Pero me preguntaba (e intentaba averiguar) si existe un límite superior aún más estricto.
Contexto: Estoy trabajando en un algoritmo mediante el cual quiero comprobar si alguno de los objetos de un conjunto de $n$ objetos, cada uno de los cuales tiene un atributo de posición, se encuentra en una trayectoria de longitud conocida entre dos puntos conocidos $a$ y $b$ . El camino se divide en $m$ segmentos de línea recta (o $m+1$ puntos si lo prefiere).
La forma más sencilla de resolver este problema es, por supuesto, simplemente comprobar cada uno de los $n$ contra cada uno de los objetos $m$ segmentos del camino. Este algoritmo sería $O(m*n)$ complejidad.
Pero me gustaría algo mejor (más eficiente) así que estaba pensando que si pudiera encontrar un límite superior como en el enunciado del problema anterior entonces podría pre-procesar la $n$ objetos para ver si cumplen el criterio del límite superior (esto sería $O(n)$ complejidad) y, a continuación, sólo comprueba los objetos que cumplen el criterio con los m segmentos (sabiendo que si no cumplen el límite superior de distancia no es posible que se encuentren en la ruta). Así, si $k$ fuera del $n$ objetos NO cumplían el criterio entonces mi algoritmo se reduciría a $O( (n-k)*m )$ complejidad. Sé que la complejidad del algoritmo en el peor de los casos seguiría siendo $O(n*m)$ pero no espero llegar a menudo a la complejidad del peor de los casos.
También soy consciente de que podría utilizar estructuras de datos espaciales para reducir la complejidad del algoritmo como una estructura de datos quadtree (esto daría $O(n*\log m)$ complejidad) pero 1) Primero me gustaría explorar soluciones más sencillas 2) el quadtree podría darme una sobrecarga no deseada (la ruta es dinámica y, por lo tanto, realizaría inserciones/eliminaciones de segmentos de ruta al quadtree regularmente 3) Este problema me parece interesante, independientemente de que acabe utilizando la solución o no :)
