Ubicación del punto

La estructura de datos más simple y temprana que logra un tiempo O(log n ) fue descubierta por Dobkin y Lipton en 1976. Se basa en subdividir S usando líneas verticales que pasan por cada vértice en S. La región entre dos líneas verticales consecutivas se llama losa . Nótese que cada losa está dividida por segmentos de línea que no se intersecan y que cruzan completamente la losa de izquierda a derecha. La región entre dos segmentos consecutivos dentro de una losa corresponde a una cara única de S. Por lo tanto, reducimos nuestro problema de localización de puntos a dos problemas más simples: ^{[ 2 ]}

1. Dada una subdivisión del plano en losas verticales, determine qué losa contiene un punto dado.
2. Dada una losa subdividida en regiones por segmentos que no se intersecan y que la atraviesan completamente de izquierda a derecha, determine qué región contiene un punto dado.

El primer problema se puede resolver mediante búsqueda binaria en la coordenada x de las líneas verticales en tiempo O(log n ). El segundo problema también se puede resolver en tiempo O(log n ) mediante búsqueda binaria. Para ver cómo, observe que, como los segmentos no se intersecan ni cruzan completamente la losa, se pueden ordenar verticalmente dentro de cada losa. Si bien este algoritmo permite la localización de puntos en tiempo logarítmico y es fácil de implementar, el espacio requerido para construir las losas y las regiones contenidas dentro de ellas puede ser tan alto como O( n² ), ya que cada losa puede cruzar una fracción significativa de los segmentos. ^{[ 2 ]}

Varios autores observaron que los segmentos que cruzan dos losas adyacentes son en su mayoría iguales. Por lo tanto, el tamaño de la estructura de datos se puede reducir significativamente. Más específicamente, Sarnak y Tarjan barren una línea vertical l de izquierda a derecha sobre el plano, manteniendo los segmentos que intersecan l en un árbol rojo-negro persistente . Esto les permite reducir el espacio de almacenamiento a O( n ), manteniendo el tiempo de consulta de O(log n ). ^{[ 3 ]}

Una cadena monótona (vertical) es un camino tal que la coordenada y nunca aumenta a lo largo del camino. Un polígono simple es monótono (vertical) si está formado por dos cadenas monótonas, con el primer y el último vértice en común. Es posible añadir algunas aristas a una subdivisión planar para que todas las caras sean monótonas, obteniendo así una subdivisión monótona. Este proceso no añade ningún vértice a la subdivisión (por lo tanto, el tamaño sigue siendo O( n )) y puede realizarse en tiempo O( n log n ) mediante barrido plano (también puede realizarse en tiempo lineal utilizando triangulación de polígonos ). Por lo tanto, no hay pérdida de generalidad si restringimos nuestra estructura de datos al caso de subdivisiones monótonas, como hacemos en esta sección.

La debilidad de la descomposición en losa radica en que las líneas verticales crean segmentos adicionales, lo que dificulta alcanzar un espacio de almacenamiento O( n ). Herbert Edelsbrunner , Leonidas J. Guibas y Jorge Stolfi descubrieron una estructura de datos óptima que utiliza únicamente las aristas en una subdivisión monótona. La idea consiste en emplear cadenas monótonas verticales, en lugar de líneas verticales, para particionar la subdivisión. ^{[ 4 ]}

Convertir esta idea general en una estructura de datos eficiente no es tarea sencilla. Primero, necesitamos poder calcular una cadena monótona que divida la subdivisión en dos mitades de tamaños similares. Segundo, dado que algunas aristas pueden estar contenidas en varias cadenas monótonas, debemos asegurarnos de que el espacio de almacenamiento sea O(n). Tercero, comprobar si un punto está a la izquierda o a la derecha de una subdivisión monótona requiere un tiempo de O( n ) si se realiza de forma ingenua. ^{[ 4 ]}

Los detalles sobre cómo resolver los dos primeros problemas están fuera del alcance de este artículo. Mencionamos brevemente cómo abordar el tercer problema. Mediante la búsqueda binaria, podemos comprobar si un punto está a la izquierda o a la derecha de una cadena monótona en tiempo O(log n ). Dado que necesitamos realizar otra búsqueda binaria anidada a través de O(log n ) cadenas para determinar la ubicación del punto, el tiempo de consulta es O(log² n). Para lograr un tiempo de consulta O(log n ), necesitamos utilizar la cascada fraccionaria , manteniendo punteros entre las aristas de diferentes cadenas monótonas. ^{[ 4 ]}

Un polígono con m vértices se puede particionar en m – 2 triángulos. Esto se puede demostrar por inducción partiendo de un triángulo. Existen numerosos algoritmos para triangular un polígono de manera eficiente, siendo el más rápido de O( n ) tiempo en el peor de los casos. Por lo tanto, podemos descomponer cada polígono de nuestra subdivisión en triángulos y restringir nuestra estructura de datos al caso de subdivisiones formadas exclusivamente por triángulos. Kirkpatrick proporciona una estructura de datos para la localización de puntos en subdivisiones trianguladas con un espacio de almacenamiento de O( n ) y un tiempo de consulta de O(log n ). ^{[ 5 ]}

La idea general es construir una jerarquía de triángulos. Para realizar una consulta, comenzamos por encontrar el triángulo de nivel superior que contiene el punto de consulta. Dado que el número de triángulos de nivel superior está limitado por una constante, esta operación se puede realizar en tiempo O(1). Cada triángulo tiene punteros a los triángulos con los que se interseca en el siguiente nivel de la jerarquía, y el número de punteros también está limitado por una constante. Procedemos con la consulta encontrando qué triángulo contiene el punto de consulta nivel por nivel. ^{[ 5 ]}

La estructura de datos se construye en orden inverso, es decir, de abajo hacia arriba. Comenzamos con la subdivisión triangulada y elegimos un conjunto independiente de vértices para eliminar. Después de eliminar los vértices, volvemos a triangular la subdivisión. Dado que la subdivisión está formada por triángulos, un algoritmo voraz puede encontrar un conjunto independiente que contenga una fracción constante de los vértices. Por lo tanto, el número de pasos de eliminación es O(log n ). ^{[ 5 ]}

Un enfoque aleatorio para este problema se basa en la descomposición trapezoidal o mapa trapezoidal. Esta descomposición se obtiene disparando balas verticales que van tanto hacia arriba como hacia abajo desde cada vértice de la subdivisión original. Las balas se detienen al chocar con una arista y forman una nueva arista en la subdivisión. De esta forma, obtenemos un subconjunto de la descomposición en losa, con solo O( n ) aristas y vértices, ya que por cada vértice de la subdivisión original solo añadimos dos nuevos vértices e incrementamos el número de aristas en cuatro. ^{[ 6 ]}

Una descomposición trapezoidal se puede construir añadiendo los segmentos de la subdivisión original, uno a uno, en orden aleatorio. Inicialmente (antes de que se haya añadido ningún segmento), la descomposición trapezoidal consiste en un único trapecio, el cuadro delimitador de la subdivisión. Cada paso subsiguiente utiliza una consulta de ubicación de puntos para localizar un extremo del siguiente segmento de línea, dentro de la descomposición trapezoidal actual, y luego recorre desde el trapecio resultante los trapecios vecinos que contienen el mismo segmento, subdividiéndolos y recombinándolos para formar la descomposición refinada. El análisis inverso , una forma de análisis comúnmente utilizada para este tipo de algoritmo de geometría incremental aleatoria, muestra que el número esperado de trapecios creados para cada inserción está limitado por una constante y, por lo tanto, que el número total de pasos de este algoritmo, excluyendo las ubicaciones de los puntos, es lineal. ^{[ 6 ]}

La localización de puntos en la subdivisión actual, realizada dentro de este algoritmo, puede hacerse utilizando la misma estructura que, al final del algoritmo, puede usarse para consultas de localización de puntos en la descomposición trapezoidal final. Esta estructura de datos de localización de puntos toma la forma de un grafo dirigido acíclico , donde los vértices son los trapecios que existían en algún momento del refinamiento, y las aristas dirigidas conectan cada trapecio que ya no está en el refinamiento con los trapecios que lo reemplazaron. Una consulta de localización de puntos se realiza siguiendo una ruta en este grafo, comenzando desde el trapecio inicial, y en cada paso eligiendo el trapecio de reemplazo que contiene el punto de consulta, hasta llegar a un trapecio que no ha sido reemplazado. La profundidad esperada de una búsqueda en este digrafo, comenzando desde cualquier punto de consulta, es O(log n ). El espacio para la estructura de datos es proporcional al número de trapecios creados a lo largo de este proceso de refinamiento, que en promedio es O( n ). ^{[ 6 ]}