El problema de localización de puntos es un tema fundamental de la geometría computacional . Encuentra aplicaciones en áreas que se ocupan del procesamiento de datos geométricos: gráficos por computadora , sistemas de información geográfica (GIS), planificación de movimiento y diseño asistido por computadora (CAD).
En su forma más general, el problema consiste, dada una partición del espacio en regiones separadas , en determinar la región donde se encuentra un punto de consulta. Por ejemplo, el problema de determinar qué ventana de una interfaz gráfica de usuario contiene un determinado clic del mouse se puede formular como un ejemplo de ubicación de puntos, con una subdivisión formada por las partes visibles de cada ventana, aunque las estructuras de datos especializadas pueden ser más apropiadas que estructuras de datos de ubicación de puntos de propósito general en esta aplicación. [1] Otro caso especial es el problema del punto en el polígono , en el que es necesario determinar si un punto está dentro, fuera o en el límite de un solo polígono .
En muchas aplicaciones, es necesario determinar la ubicación de varios puntos diferentes con respecto a la misma partición del espacio. Para resolver este problema de manera eficiente, es útil construir una estructura de datos que, dado un punto de consulta, determine rápidamente qué región contiene el punto de consulta (por ejemplo, diagrama de Voronoi ).
En el caso plano, se nos da una subdivisión plana S , formada por múltiples polígonos llamados caras, y necesitamos determinar qué cara contiene un punto de consulta. Es posible realizar una búsqueda de fuerza bruta de cada cara utilizando el algoritmo de punto en polígono , pero normalmente no es factible para subdivisiones de alta complejidad. Varios enfoques diferentes conducen a estructuras de datos óptimas, con O ( n ) espacio de almacenamiento y O (log n ) tiempo de consulta, donde n es el número total de vértices en S. Por simplicidad, asumimos que la subdivisión plana está contenida dentro de un cuadro delimitador cuadrado.
Dobkin y Lipton descubrieron la estructura de datos más simple y temprana para lograr el tiempo O (log n ) 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 . Observe que cada losa está dividida por segmentos de línea que no se cruzan y que cruzan completamente la losa de izquierda a derecha. La región entre dos segmentos consecutivos dentro de una losa corresponde a una única cara de S. Por lo tanto, reducimos nuestro problema de ubicación de puntos a dos problemas más simples: [2]
El primer problema se puede resolver mediante una 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 cruzan y cruzan completamente la losa, los segmentos se pueden ordenar verticalmente dentro de cada losa. Si bien este algoritmo permite la ubicació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 las losas puede ser tan alto como O ( n² ), ya que cada losa puede cruzar una fracción significativa del segmentos. [2]
Varios autores observaron que los segmentos que cruzan dos losas adyacentes son en su mayoría iguales. Por 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 cruzan l en un árbol rojo-negro persistente . Esto les permite reducir el espacio de almacenamiento a O( n ), manteniendo el tiempo de consulta 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 último vértice en común. Es posible agregar algunas aristas a una subdivisión plana, para que todas las caras sean monótonas, obteniendo lo que se llama una subdivisión monótona. Este proceso no agrega ningún vértice a la subdivisión (por lo tanto, el tamaño permanece O( n )) y se puede realizar en tiempo O( n log n ) mediante barrido plano (también se puede realizar en tiempo lineal, usando 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 lo hacemos en esta sección.
La debilidad de la descomposición de losas es que las líneas verticales crean segmentos adicionales en la descomposición, lo que dificulta lograr O ( n ) espacio de almacenamiento. Herbert Edelsbrunner , Leonidas J. Guibas y Jorge Stolfi descubrieron una estructura de datos óptima que solo utiliza los bordes en una subdivisión monótona. La idea es utilizar cadenas verticales monótonas, en lugar de utilizar líneas verticales para dividir la subdivisión. [4]
Convertir esta idea general en una estructura de datos realmente eficiente no es una tarea sencilla. Primero, debemos poder calcular una cadena monótona que divida la subdivisión en dos mitades de tamaños similares. En segundo lugar, dado que algunos bordes pueden estar contenidos en varias cadenas monótonas, debemos tener cuidado de garantizar que el espacio de almacenamiento sea O (n). En tercer lugar, comprobar si un punto está en el lado izquierdo o derecho de una subdivisión monótona lleva O( n ) tiempo 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 tema. Usando la búsqueda binaria, podemos probar si un punto está a la izquierda o a la derecha de una cadena monótona en tiempo O (log n ). Como necesitamos realizar otra búsqueda binaria anidada a través de cadenas O (log n ) para determinar realmente la ubicación del punto, el tiempo de consulta es O (log² n). Para lograr un tiempo de consulta O (log n ), necesitamos usar cascada fraccionaria , manteniendo punteros entre los bordes de diferentes cadenas monótonas. [4]
Un polígono con m vértices se puede dividir en m –2 triángulos. Lo cual se puede demostrar por inducción a partir de un triángulo. Existen numerosos algoritmos para triangular un polígono de manera eficiente; el más rápido tiene O( n ) el peor tiempo de caso. Por 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 ubicación de puntos en subdivisiones trianguladas con O ( n ) espacio de almacenamiento y O(log n ) tiempo de consulta. [5]
La idea general es construir una jerarquía de triángulos. Para realizar una consulta, comenzamos buscando 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 que intersecta 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 el orden opuesto, 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, retriangulamos la subdivisión. Debido a que la subdivisión está formada por triángulos, un algoritmo codicioso 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. Se obtiene una descomposición trapezoidal disparando balas verticales que suben y bajan desde cada vértice de la subdivisión original. Las balas se detienen cuando golpean un borde y forman un nuevo borde en la subdivisión. De esta manera, obtenemos un subconjunto de la descomposición de la losa, con solo O( n ) aristas y vértices, ya que por cada vértice en la subdivisión original solo agregamos dos nuevos vértices y aumentamos el número de aristas en cuatro. [6]
Se puede construir una descomposición trapezoidal sumando los segmentos de la subdivisión original, uno por uno, en orden aleatorio. Inicialmente (antes de que no se hayan agregado segmentos), la descomposición trapezoidal consta de un solo trapezoide, el cuadro delimitador de la subdivisión. Cada paso posterior utiliza una consulta de ubicación de puntos para localizar un punto final del siguiente segmento de línea, dentro de la descomposición trapezoidal actual, y luego camina desde el trapezoide resultante hasta los trapecios vecinos que contienen el mismo segmento, subdividiéndolos y recombinándolos para formar la descomposición refinada. El análisis hacia atrás, 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, fuera del ubicaciones de puntos, es lineal. [6]
Las ubicaciones de puntos en la subdivisión actual, realizadas dentro de este algoritmo, se pueden realizar usando la misma estructura que, al final del algoritmo, se puede usar para consultas de ubicación de puntos en la descomposición trapezoidal final. Esta estructura de datos de ubicación de puntos toma la forma de un gráfico acíclico dirigido , donde los vértices son los trapecios que existieron en algún momento del refinamiento, y los bordes dirigidos conectan cada trapezoide que ya no está en el refinamiento con los trapecios que lo reemplazaron. Una consulta de ubicación de un punto se realiza siguiendo una ruta en este gráfico, comenzando desde el trapecio inicial y eligiendo en cada paso el trapezoide de reemplazo que contiene el punto de consulta, hasta llegar a un trapezoide que no ha sido reemplazado. La profundidad esperada de una búsqueda en este dígrafo, 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 se espera que sea O ( n ). [6]
No se conocen estructuras de datos de ubicación de puntos generales con espacio lineal y tiempo de consulta logarítmico para dimensiones mayores que 2 [ cita requerida ] . Por lo tanto, debemos sacrificar el tiempo de consulta o el espacio de almacenamiento, o limitarnos a algún tipo de subdivisión menos general.
En el espacio tridimensional, es posible responder consultas de ubicación de puntos en O(log² n ) utilizando el espacio O( n log n ). La idea general es mantener varias estructuras de datos de ubicación de puntos planos, correspondientes a la intersección de la subdivisión con n planos paralelos que contienen cada vértice de la subdivisión. Un uso ingenuo de esta idea aumentaría el espacio de almacenamiento a O ( n ²). De la misma manera que en la descomposición de losa, la similitud entre estructuras de datos consecutivas se puede explotar para reducir el espacio de almacenamiento a O ( n log n ), pero el tiempo de consulta aumenta a O (log² n ). [ cita necesaria ]
En un espacio d -dimensional, la ubicación del punto se puede resolver proyectando recursivamente las caras en un espacio ( d -1)-dimensional. Si bien el tiempo de consulta es O (log n ), el espacio de almacenamiento puede ser tan alto como . La alta complejidad de las estructuras de datos d -dimensionales llevó al estudio de tipos especiales de subdivisión.
Un ejemplo importante es el caso de las disposiciones de hiperplanos . Una disposición de n hiperplanos define O( n d ) celdas, pero la ubicación del punto se puede realizar en O(log n ) tiempo con O( n d ) espacio utilizando los cortes jerárquicos de Chazelle .
Otro tipo especial de subdivisión se llama subdivisión rectilínea (u ortogonal). En una subdivisión rectilínea, todas las aristas son paralelas a uno de los ejes ortogonales d . En este caso, la ubicación del punto se puede responder en tiempo O(log d -1 n ) con espacio O( n ).
