La ruta más corta en la poligonal de dominio

Question

El único disparo de consulta para el camino más corto entre dos puntos en un plano medio ambiente con la poligonal de los obstáculos de la complejidad de la $O(n)$ puede ser resuelto en tiempo $O(n \log n)$ mediante la continua Dijkstra método.

¿Qué sucede si estoy dado un conjunto $P$ $k$ puntos en el plano, y quiero preprocesar ellos, s.t. el camino más corto entre dos puntos cualesquiera en $P$ puede ser calculada de manera eficiente. Existen algoritmos conocidos para este problema?

Gracias

Stefan

Answer 1

El papel por Chiang y Mitchell, "Dos-Punto Euclidiana Camino más Corto Consultas en el Avión" (1999), puede responder a su pregunta:

Dado un conjunto $h$ de obstáculos poligonales en el plano, teniendo un total de $n$ vértices, construir una estructura de datos tal que para cualesquiera dos de la consulta de los puntos de $s$ $t$ que de manera eficiente puede determinar la longitud de la ... de un Euclidiana menor obstáculo, evitando el camino ... de$s$$t$. ... Se presentan varios métodos para resolver este dos-punto de consulta problema, incluyendo los algoritmos con $o(n)$, $O(\log n+h)$, $O(h \log n)$, $O(\log^2 n)$ o óptimas $O(\log n)$ tiempos de consulta, mediante el polinomio de espacio de estructuras de datos, con distintos equilibrios entre el espacio y el tiempo de consulta.

En su caso (puntos en lugar de obstáculos poligonales), $h=n$.