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 una gran importancia práctica si se utilizan algoritmos en conjuntos de datos muy grandes que contienen decenas o cientos de millones de puntos. Para estos 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 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 de movimiento y problemas de visibilidad), los sistemas de información geográfica (SIG) (ubicación y búsqueda geométrica, planificación de rutas), el diseño de circuitos integrados (diseño y verificación de geometría de CI), la ingeniería asistida por computadora (generación de mallas) y la 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 los consideraba problemas 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 toma 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 proporciona una entrada y es necesario construir o encontrar la salida correspondiente. Algunos problemas fundamentales de este tipo son:
La complejidad computacional para 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 la consulta , que varía según las instancias del problema. El espacio de búsqueda normalmente debe preprocesarse de manera que se puedan responder varias 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 generalmente involucran 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 al proporcionar la adición y/o eliminación de los puntos. El problema de envoltura convexa dinámica es realizar un seguimiento de la envoltura convexa, 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 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 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 en qué área de la pantalla se hace clic con 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 la 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. Finalmente, en el ejemplo de gráficos por ordenador 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 aprovecharse para lograr estructuras de datos eficientes o para realizar estimaciones de complejidad computacional más precisas. 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 en este caso 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 conjunto de niveles .
Las áreas de aplicación de la geometría computacional incluyen la construcción naval, la aeronáutica y la industria automotriz.
A continuación se muestra la lista de las principales revistas que han publicado 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 y gráficos computacionales de uso general disminuyó.
