computational geometry - Diferencia entre quadtree y kd-tree.

computational-geometry kdtree

Question

¿Cuál es la principal diferencia entre un quadtree y un kd-tree? Entiendo que dividen puntos en muchas dimensiones, pero no entiendo por qué usaríamos uno sobre el otro. Necesito una estructura que me permita contar cuántos puntos (puntos 2D) hay en una región determinada. Básicamente, estoy tratando de detectar grupos de puntos.

Answer 1

La diferencia (algorítmicamente) es: en quadtrees, los datos que llegan a un nodo se dividen en celdas fijas (2 ^ d) de igual tamaño, mientras que en kdtrees, los datos se dividen en dos regiones según un análisis de datos (por ejemplo, la mediana de alguna coordenada). Los quadtrees no escalan bien a dimensiones altas, debido a la dependencia exponencial en la dimensión. Las estructuras de datos también difieren en sus complejidades de tiempo de consulta.

Ya que estás interesado en los puntos 2D, cualquiera de las estructuras de datos puede funcionar para ti. Los árboles KD son muy fáciles de consultar para los rangos, y generalmente se prefieren a los quadtrees. Te sugiero que los uses.