Estructura de datos eficiente para la distancia euclidiana más cercana

Question

La pregunta está inspirada en el siguiente problema de la UVA: https : //onlinejudge.org/index.php? Opción= OnlineJudge & Amp; ItemID= 99999999 & Categoría= 18 & Page= show_problem & problem= 1628 .

Una red de estaciones de adquisición de datos autónoma, alimentada por batería, se ha instalado para monitorear el clima en la región de Amazon. Una estación de envío de orden puede iniciar la transmisión de instrucciones a las estaciones de control para que cambien sus parámetros actuales. Para evitar sobrecargar la batería, cada estación (incluida la estación de envío de pedidos) solo puede transmitir a otras dos estaciones. Los destinatarios de una estación son las dos estaciones más cercanas. En caso de sorteo, el primer criterio es elegir al más occidental (más a la izquierda en el mapa), y el segundo criterio es elegir el más al sur (más bajo en el mapa). Usted está encargado por el gobierno del Estado de Amazon para escribir un programa que decida si, dada la localización de cada estación, los mensajes pueden llegar a todas las estaciones.

El algoritmo ingenuo, por supuesto, construiría un gráfico con las estaciones como vértices y calcularía los bordes de un vértice dado al buscar a través de todos los demás vértices para los dos más cercanos. Luego, simplemente podríamos ejecutar DFS / BFS. Por supuesto, esto toma $ o (v ^ 2) $ tiempo para construir el gráfico (que pasa los casos de prueba). Sin embargo, mi pregunta es si podemos construir el gráfico más rápido con una estructura de datos apropiada. Específicamente, dado un punto de consulta arbitraria $ p $ y un conjunto dado de puntos $ s $ podemos Organice los puntos en $ s $ de tal manera que podemos encontrar rápidamente los dos puntos más cercanos en $ s $ a $ P $ (Diga, en $ \ log v $ tiempo?).

Answer 1

Si entiendo esto correctamente, se podrían usar la mayoría de los índices espaciales.

Los índices espaciales generalmente tienen alrededor de $ o (registro {v}) $ Tiempo de inserción y tiempo de búsqueda similar para los vecinos más cercanos. Por supuesto, puede crear un diagrama Voronoi a partir de eso, pero también puede usar el índice directamente para encontrar a los vecinos más cercanos cada vez que los necesite.

Para baja dimensionalidad (2D, 3D), las familias comunes de los índices espaciales son kd-arboles (bastante simple y generalmente bueno, pero tiende a tener problemas con grupos densos de puntos), quadtrees (un poco más difícil de implementarse porque la precisión numérica puede ser complicada) y r-tree (más difícil de implementar, pero dar mejor desempeño garantizado, especialmente el árbol R * (R-Star-Tree).

En caso de que esté utilizando C ++, eche un vistazo a libspatialindex o el Boost R-Tree . Si está utilizando Java, eche un vistazo a mi Tinspin biblioteca.

El término técnico para esto es " $ k $ consultas vecinas más cercanas" o " $ k $ -Nn consultas ", con $ k $ refiriéndose a la cantidad de vecinos más cercanos que desea encontrar.

Answer 2

Parece que la estructura de datos relevante podría ser una dinámica diagrama voronoi .

Los diagramas Voronoi son a menudo la respuesta cuando se involucra un conjunto de puntos en el plano.

En este caso, dado que el conjunto de puntos está evolucionando, desea una versión dinámica.