data structures - disjoint - Estructura de datos para búsqueda rápida de intervalos de tiempo

data structures pdf

Question

Tengo un conjunto de intervalos de tiempo In = (an, bn) . Necesito realizar muchas búsquedas donde me den un tiempo t y necesito devolver rápidamente los intervalos que contienen t , por ejemplo, esos intervalos tales que un <= t <= bn .

¿Qué es una buena estructura de datos o algoritmo para esto?

Si importa, en mi caso los an y bn son enteros.

Answer 1

Esta es básicamente una cuestión de partición de espacio. Tiene un espacio grande con contenedores y un punto específico en ese espacio, ¿qué contenedores toca? Muchos juegos tienen que resolver este problema, por lo que no sería una mala idea comenzar allí. Busque artículos sobre "Detección de colisión de fase amplia".

La forma más sencilla de hacerlo es dividir el espacio numérico en un número constante de piezas. Cada pieza sabe qué conjuntos se intersectan con ella, algo que se calcula cada vez que se agrega un nuevo conjunto. Ahora, en lugar de probar cada conjunto cuando tiene un punto, solo necesita verificar los conjuntos contenidos en la pieza en la que se encuentra el punto.

Otro algoritmo general y eficiente utilizado es la división de espacios binarios. Este algoritmo subdivide su espacio en dos lados. Cada lado sabría qué conjuntos se intersecan con él. Puede repetir este proceso de forma recursiva con la precisión deseada (aunque no tiene sentido crear una subdivisión más pequeña que el rango de su conjunto más pequeño).

Answer 2

Le invitamos a consultar la implementación de C # que he publicado en CodePlex para IntervalTree que resuelve este problema exactamente.

Hago.

Answer 3

Lo que está buscando es un árbol de intervalos (que es un tipo de árbol de rango ).

Estos tienen un tiempo de búsqueda logarítmica como otras estructuras de árbol (por ejemplo, árboles RB), por lo que debería ver un rendimiento comparable al uso de algo como un Mapa de árbol de Java o un mapa STL.

• Código para árboles rojo-negro y árboles de intervalo de MIT
• Hay una implementación de C ++ en la Biblioteca de CGAL .
• Aquí hay una implementación de C #

Answer 4

Su problema es solo unidimensional, por lo que es un poco más simple que los problemas de partición de espacio que se encuentran en la mayoría de los juegos. Podría tener solo un BST simple y en cada hoja recuerde la lista de intervalos a la izquierda de la hoja.

si tuviera intervalos A (0, 10) y B (5, 15), entonces las hojas del árbol serían (0 con la lista vacía), (5 con A), (10 con A, B) y (15 con SEGUNDO).