El objetivo principal de la investigación en geometría computacional combinatoria es desarrollar algoritmos y estructuras de datos eficientes para resolver problemas planteados en términos de objetos geométricos básicos: puntos, segmentos de línea, polígonos, poliedros, etc.
Algunos de estos problemas parecen tan sencillos que no se consideraban problemas hasta la llegada de los ordenadores. Consideremos, por ejemplo, el problema del par más cercano:
- Dados n puntos en el plano, encuentre los dos con la menor distancia entre sí.
Uno podría calcular las distancias entre todos los pares de puntos, de los cuales hay n(n-1)/2, y luego elegir el par con la menor distancia. Este algoritmo de fuerza bruta requiere un tiempo O(n2), es decir, su tiempo de ejecución es proporcional al cuadrado del número de puntos. Un resultado clásico en geometría computacional fue la formulación de un algoritmo que tarda O(n log n). También se han descubierto algoritmos aleatorios que toman O(n) de tiempo esperado, así como un algoritmo determinista que toma O(n log n) de tiempo.
Clases de problemasEditar
Los problemas centrales de la geometría computacional pueden clasificarse de diferentes maneras, según diversos criterios. Se pueden distinguir las siguientes clases generales.
Problemas estáticosEditar
En los problemas de esta categoría, se da alguna entrada y se necesita construir o encontrar la salida correspondiente. Algunos problemas fundamentales de este tipo son:
- Casco convexo: Dado un conjunto de puntos, encontrar el menor poliedro/polígono convexo que contenga todos los puntos.
- Intersección de segmentos de línea: Encontrar las intersecciones entre un conjunto dado de segmentos de línea.
- Triangulación de Delaunay
- Diagrama de Voronoi: Dado un conjunto de puntos, particionar el espacio según los puntos más cercanos a los puntos dados.
- Programación lineal
- Par de puntos más cercanos: Dado un conjunto de puntos, encontrar los dos con menor distancia entre sí.
- Par de puntos más lejano
- Círculo vacío más grande: Dado un conjunto de puntos, encontrar un círculo más grande con su centro dentro de su casco convexo y que no encierre a ninguno de ellos.
- Camino más corto euclidiano: Conectar dos puntos en un espacio euclidiano (con obstáculos poliédricos) mediante un camino más corto.
- Triangulación de polígonos: Dado un polígono, particionar su interior en triángulos
- Generación de mallas
- Operaciones booleanas sobre polígonos
La complejidad computacional para esta clase de problemas se estima por el tiempo y el espacio (memoria del ordenador) necesarios para resolver una instancia de problema dada.
Problemas de consulta geométricaEditar
En los problemas de consulta geométrica, comúnmente conocidos como problemas de búsqueda geométrica, la entrada consta de dos partes: la parte del espacio de búsqueda y la parte de la consulta, que varía sobre las instancias del problema. El espacio de búsqueda normalmente necesita ser preprocesado, de manera que múltiples consultas puedan ser respondidas eficientemente.
Algunos problemas de consulta geométrica fundamentales son:
- Búsqueda de rango: Preprocesar un conjunto de puntos, con el fin de contar eficientemente el número de puntos dentro de una región de consulta.
- Localización de puntos: Dada una partición del espacio en celdas, producir una estructura de datos que diga eficientemente en qué celda se encuentra un punto de consulta.
- Vecino más cercano: Preprocesar un conjunto de puntos, con el fin de encontrar eficientemente qué punto es el más cercano a un punto de consulta.
- Trazado de rayos: Dado un conjunto de objetos en el espacio, producir una estructura de datos que diga eficientemente qué objeto interseca primero un rayo de consulta.
Si el espacio de búsqueda es fijo, la complejidad computacional para esta clase de problemas suele estimarse por:
- el tiempo y el espacio necesarios para construir la estructura de datos en la que se busca
- el tiempo (y a veces un espacio extra) para responder a las consultas.
Para el caso en el que se permite que el espacio de búsqueda varíe, véase «Problemas dinámicos».
Problemas dinámicosEditar
Otra clase importante son los problemas dinámicos, en los que el objetivo es encontrar un algoritmo eficiente para encontrar una solución repetidamente tras cada modificación incremental de los datos de entrada (adición o eliminación de elementos geométricos de entrada). Los algoritmos para problemas de este tipo suelen implicar estructuras de datos dinámicas. Cualquiera de los problemas geométricos computacionales puede convertirse en uno dinámico, a costa de un mayor tiempo de procesamiento. Por ejemplo, el problema de búsqueda de rangos puede convertirse en un problema dinámico de búsqueda de rangos, previendo la adición y/o la eliminación de los puntos. El problema del casco convexo dinámico consiste en mantener el seguimiento del casco convexo, por ejemplo, para el conjunto de puntos que cambia dinámicamente, es decir mientras se insertan o eliminan los puntos de entrada.
La complejidad computacional para esta clase de problemas se estima por:
- el tiempo y el espacio necesarios para construir la estructura de datos en la que se busca
- el tiempo y el espacio para modificar la estructura de datos buscada después de un cambio incremental en el espacio de búsqueda
- el tiempo (y a veces un espacio adicional) para responder a una consulta.
VariacionesEditar
Algunos problemas pueden ser tratados como pertenecientes a cualquiera de las categorías, dependiendo del contexto. Por ejemplo, considere el siguiente problema.
- Punto en polígono: Decidir si un punto está dentro o fuera de un polígono dado.
En muchas aplicaciones este problema se trata como un problema de una sola vez, es decir, perteneciente a la primera clase. Por ejemplo, en muchas aplicaciones de gráficos por ordenador un problema común es encontrar qué área de la pantalla es pulsada por un puntero. Sin embargo, en algunas aplicaciones, el polígono en cuestión es invariable, mientras que el punto representa una consulta. Por ejemplo, el polígono de entrada puede representar una frontera de un país y un punto es la posición de un avión, y el problema es determinar si el avión violó la frontera. Por último, en el ejemplo anteriormente mencionado de los gráficos por ordenador, en las aplicaciones CAD los datos de entrada cambiantes se almacenan a menudo en estructuras de datos dinámicas, que pueden ser explotadas para acelerar las consultas punto-en-polígono.
En algunos contextos de problemas de consulta hay expectativas razonables sobre la secuencia de las consultas, que pueden ser explotadas para estructuras de datos eficientes o para estimaciones de complejidad computacional más ajustadas. Por ejemplo, en algunos casos es importante conocer el peor caso para el tiempo total para toda la secuencia de N consultas, en lugar de para una sola consulta. Véase también «análisis amortizado».