La geometría computacional es una rama de la informática dedicada al estudio de algoritmos que pueden expresarse en términos de geometría . Algunos problemas puramente geométricos surgen del estudio de algoritmos geométricos computacionales , y dichos problemas también se consideran parte de la geometría computacional. Si bien la geometría computacional moderna es un desarrollo reciente, es uno de los campos más antiguos de la informática con una historia que se remonta a la antigüedad.
La complejidad computacional es fundamental para la geometría computacional, y tiene gran importancia práctica si los algoritmos se utilizan en conjuntos de datos muy grandes que contienen decenas o cientos de millones de puntos. Para tales conjuntos, la diferencia entre O( n 2 ) y O( n log n ) puede ser la diferencia entre días y segundos de cálculo.
El principal impulso para el desarrollo de la geometría computacional como disciplina fue el progreso en los gráficos por computadora y el diseño y la fabricación asistidos por computadora ( CAD / CAM ), pero muchos problemas en la geometría computacional son de naturaleza clásica y pueden provenir de la visualización matemática .
Otras aplicaciones importantes de la geometría computacional incluyen la robótica ( planificación del movimiento y problemas de visibilidad), sistemas de información geográfica (GIS) (ubicación y búsqueda geométrica, planificación de rutas), diseño de circuitos integrados (diseño y verificación de geometría IC), ingeniería asistida por computadora (CAE) (generación de malla) y visión por computadora ( reconstrucción 3D ).
Las principales ramas de la geometría computacional son:
Aunque la mayoría de los algoritmos de geometría computacional se han desarrollado (y se están desarrollando) para computadoras electrónicas, algunos algoritmos se desarrollaron para computadoras no convencionales (por ejemplo, computadoras ópticas [3] ).
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 simples que no se consideraron problemas en absoluto hasta la llegada de las computadoras . Consideremos, por ejemplo, el problema del par más cercano :
Se podrían calcular las distancias entre todos los pares de puntos, de los cuales hay n(n-1)/2 , y luego elegir el par con la distancia más pequeña. Este algoritmo de fuerza bruta requiere O ( n 2 ) tiempo; 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 toma O ( n log n ). También se han descubierto algoritmos aleatorios que toman O( n ) tiempo esperado, [4] así como un algoritmo determinista que toma O( n log log n ) tiempo, [5] .
Los problemas centrales de la geometría computacional pueden clasificarse de diferentes maneras, según diversos criterios. Se pueden distinguir las siguientes clases generales.
En los problemas de esta categoría, se dan algunas entradas y es necesario construir o encontrar la salida correspondiente. Algunos problemas fundamentales de este tipo son:
La complejidad computacional de esta clase de problemas se estima mediante el tiempo y el espacio (memoria de la computadora) necesarios para resolver una instancia de problema determinada.
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 consulta , que varía según las instancias del problema. Por lo general, el espacio de búsqueda necesita ser preprocesado , de manera que se puedan responder múltiples consultas de manera eficiente.
Algunos problemas fundamentales de consulta geométrica son:
Si el espacio de búsqueda es fijo, la complejidad computacional para esta clase de problemas generalmente se estima mediante:
Para el caso en el que se permite variar el espacio de búsqueda, consulte "Problemas dinámicos".
Otra clase importante son los problemas dinámicos , en los que el objetivo es encontrar un algoritmo eficiente para encontrar una solución repetidamente después de 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 normalmente implican estructuras de datos dinámicas . Cualquiera de los problemas geométricos computacionales se puede convertir en uno dinámico, a costa de un mayor tiempo de procesamiento. Por ejemplo, el problema de búsqueda de rango se puede convertir en el problema de búsqueda de rango dinámico proporcionando la adición y/o eliminación de puntos. El problema del casco convexo dinámico es realizar un seguimiento del casco convexo, por ejemplo, para el conjunto de puntos que cambian dinámicamente, es decir, mientras se insertan o eliminan los puntos de entrada.
La complejidad computacional para esta clase de problemas se estima mediante:
Algunos problemas pueden considerarse pertenecientes a cualquiera de las categorías, según el contexto. Por ejemplo, considere el siguiente problema.
En muchas aplicaciones, este problema se trata como un problema de un solo disparo, es decir, perteneciente a la primera clase. Por ejemplo, en muchas aplicaciones de gráficos por computadora , un problema común es encontrar en qué área de la pantalla se hace clic con un puntero . Sin embargo, en algunas aplicaciones, el polígono en cuestión es invariante, mientras que el punto representa una consulta. Por ejemplo, el polígono de entrada puede representar la frontera de un país y un punto es la posición de una aeronave, y el problema es determinar si la aeronave violó la frontera. Finalmente, en el ejemplo de gráficos por computadora mencionado anteriormente, en las aplicaciones CAD los datos de entrada cambiantes a menudo se almacenan en estructuras de datos dinámicas, que pueden aprovecharse para acelerar las consultas de puntos en polígonos.
En algunos contextos de problemas de consulta existen expectativas razonables sobre la secuencia de las consultas, que pueden explotarse para estructuras de datos eficientes o para estimaciones de complejidad computacional más estrictas. Por ejemplo, en algunos casos es importante conocer el peor caso para el tiempo total de toda la secuencia de N consultas, en lugar de para una sola consulta. Véase también " análisis amortizado ".
Esta rama también se conoce como modelado geométrico y diseño geométrico asistido por computadora (CAGD).
Los problemas centrales son el modelado y la representación de curvas y superficies.
Los instrumentos más importantes aquí son las curvas paramétricas y las superficies paramétricas , como las curvas de Bézier , las curvas spline y las superficies. Un enfoque no paramétrico importante es el método de fijación de niveles .
Las áreas de aplicación de la geometría computacional incluyen la construcción naval, la aviación y la industria automotriz.
A continuación se muestra la lista de las principales revistas que han estado publicando investigaciones sobre algoritmos geométricos. Tenga en cuenta que con la aparición de revistas dedicadas específicamente a la geometría computacional, la proporción de publicaciones geométricas en revistas de informática de propósito general y gráficas por computadora disminuyó.
