Árbol de segmento

Permite consultar cuál de los segmentos guardados contiene un punto.

Sea S un conjunto de intervalos o segmentos.

La región de esta división es llamada intervalos elementales.

Puntos por separados son tratados como intervalos porque la respuesta a una consulta no es necesariamente la misma en el interior de un intervalo elemental que en sus puntos extremos.

Para lograr esto, los intervalos en I son insertados uno por uno en el árbol de segmento.

Una consulta para un árbol de segmento, recibe un punto qx y recupera una lista de todos los segmentos almacenados que contienen el punto qx.

[8]​ Una versión multidimensional del árbol de intervalo es árbol de búsqueda con prioridad y no existe, es decir, no hay ninguna extensión clara de estas estructuras que solucione el problema análogo multidimensional.

[6]​ El árbol de segmento fue descubierto por J. L. Bentley en 1977; en "Solutions to Klee’s rectangle problems".