Algoritmos en pocas palabras, 2ª edición

Capítulo 10. Estructuras de árbol espaciales

Este trabajo se ha traducido utilizando IA. Agradecemos tus opiniones y comentarios: [e-mail]

Los algoritmos de este capítulo se ocupan principalmente de modelar estructuras bidimensionales sobre el plano cartesiano para realizar potentes consultas de búsqueda que van más allá de la simple pertenencia, como se trata en el capítulo 5. Estos algoritmos incluyen:

Vecino más próximo

Dado un conjunto de puntos bidimensionales, P, determina qué punto está más cerca de un punto de consulta objetivo, x. Esto puede resolverse en O(log n) en lugar de una solución de fuerza bruta O(n).

Consultas de rango

Dado un conjunto de puntos bidimensionales, P, determina qué puntos están contenidos en una región rectangular dada. Esto puede resolverse en O(n0^,5 + r), donde r es el número de puntos indicados, en lugar de una solución de fuerza bruta O(n).

Consultas de intersección

Dado un conjunto de rectángulos bidimensionales, R, determina qué rectángulos intersecan una región rectangular objetivo. Esto puede resolverse en O(log n) en lugar de una solución de fuerza bruta O(n).

Detección de colisión

Dado un conjunto de puntos bidimensionales, P, determina las intersecciones entre cuadrados de lado s centrados en dichos puntos. Esto puede resolverse en O(n log n) en lugar de una solución de fuerza bruta O(ⁿ²).

Las estructuras y los algoritmos se extienden naturalmente a múltiples dimensiones, pero este capítulo se limitará ...