Estructura de datos espaciales rápidos para la búsqueda de vecinos más cercanos entre hiperesferas de tamaño no uniforme

Dado un espacio bidimensional continuo (euclidiano) lleno de hyperspheres en movimiento/crecimiento/contracción bastante impredecibles Necesito encontrar repetidamente la hiperesfera cuya superficie es la más cercana a un coordenada dada Si algunas hiperesferas están a la misma distancia de mi coordenada, entonces la mayor hiperesfera gana. (El recuento total de hiperesferas está garantizado para permanecer igual en el tiempo.)Estructura de datos espaciales rápidos para la búsqueda de vecinos más cercanos entre hiperesferas de tamaño no uniforme

Mi primera idea fue utilizar un KDTree pero no va a tener volúmenes no uniformes los hiperesferas en cuenta. Así que busqué más y encontré BVH (Jerarquías de volumen delimitador) y BIH (Jerarquías de intervalo delimitador), que parecen hacer el truco. Al menos en el espacio de 2/3 dimensiones. Sin embargo, al encontrar bastante información y visualizaciones en los BVH, apenas pude encontrar nada en los BIH.

Mi requisito básico es un k-dimensional estructura de datos espaciales que toma en cuenta el volumen y de que sea súper rápido para construir (fuera de línea) o dinámicas con casi cualquier desequilibrio.

Dados mis requisitos anteriores, ¿con qué estructura de datos irías? ¿Algún otro que ni siquiera mencioné?

Edición 1: ¿Ha olvidado mencionar: se permite hypershperes (en realidad altamente esperado) para solapar!

Editar 2: Parece que en lugar de "distancia" (y "distancia negativa" en particular) mi métrica descrita coincide con la power of a point mucho mejor.

Fuente

2012-06-04 Regexident

Dado que calcular la distancia de un punto a una hiperesfera es completamente trivial (incluso si O (k), pero de esa manera es todo en k-espacio), ¿cuántas hypersferas tiene en general? Por supuesto, la estructura de datos debe pagar, en comparación con una simple lista lineal de hiperesferas. Buena pregunta, sin embargo. –

El número de hiperesferas podría ser 8 (en cuyo caso probablemente solo usaría la fuerza bruta, o en miles, o incluso cientos de miles, dependiendo del tamaño del conjunto de datos, que en este momento no puedo prever. Actualmente estoy haciendo fuerza bruta y es tremendamente lento. – Regexident

¿El número de hiperesferas cambia a medida que se ejecuta el programa? Y, para mayor claridad, cuando escribe 'una determinada coordenada', espero que quiera decir que quiere una función que, para cualquier coordenada dada, devuelve la hiperesfera más cercana. Es decir, la coordenada dada no se fija durante la duración del programa? –

Espero que un QuadTree/Octree/generalizado a 2^K-tree para su dimensionalidad de K haría el truco; estos espacios de partición recursiva, y presumiblemente pueden detenerse cuando un subcubo K (o un bloque K-rectangular si las divisiones no son pares) no contiene una hiperesfera, o contiene una o más hiperesferas de modo que el particionamiento no separa ninguna, o alternativamente contiene el centro de una sola hiperesfera (probablemente más fácil).

Insertar y eliminar entidades en dichos árboles es rápido, por lo que un tamaño de cambio de hiperesfera solo causa un par de operaciones de eliminar/insertar. (Sospecho que puedes optimizar esto si el tamaño de tu esfera cambia por partición recursiva adicional local si la esfera se hace más pequeña, o fusionando K-bloque local si crece).

No he trabajado con ellos, pero también podría considerar binary space partitions. Estos le permiten usar árboles binarios en lugar de k-árboles para particionar su espacio. Entiendo que los KDTrees son un caso especial de esto.

Pero, en cualquier caso, pensé que los algoritmos de inserción/eliminación para 2^K trees y/o BSP/KDTrees se entendían bien y eran rápidos. Entonces, los cambios en el tamaño de la hiperesfera provocan operaciones de eliminación/inserción, pero son rápidos. Entonces no entiendo tu objeción a los árboles KD.

Creo que el rendimiento de todos estos son asintóticamente iguales.

Fuente

2012-06-07 12:38:10

¿Cómo funcionaría la partición de espacio y/o 2^k-trees con el hecho de que se espera que las hiperesferas se superpongan (y esto con frecuencia)? Lo siento si esto no estaba claro. Edité mi pregunta para reflejar mejor eso. – Regexident

¿Por qué es importante su superposición? Todo lo que quiere hacer es dividir el espacio de modo que un pequeño conjunto de esferas esté en un trozo particular, de modo que pueda decidir cuál es el mejor para la coordenada en ese trozo. Y si la superposición te molesta, entonces particiona hasta que un K-block contenga solo el punto central de una esfera. Luego encuentre la partición que contiene su punto de interés y enumere todos los sub-bloques que contienen esferas/spherecenterpoints. –

¿Eso sería turboalimentado o solo 200 galones? –

Usaría la extensión R * Tree para SQLite. Una tabla normalmente tendría 1 o 2 datos dimensionales. Las consultas SQL pueden combinar varias tablas para buscar en dimensiones superiores.

La formulación con distancia negativa es un poco rara.La distancia es positiva en geometría, por lo que puede no haber mucha teoría útil para usar.

Una formulación diferente que utiliza solo distancias positivas puede ser útil. Lea sobre espacios hiperbólicos. Esto podría ayudar a proporcionar ideas para otras formas de describir la distancia.

Fuente

2012-06-11 20:33:02

Estructura de datos espaciales rápidos para la búsqueda de vecinos más cercanos entre hiperesferas de tamaño no uniforme

Respuesta

Cuestiones relacionadas