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 los algoritmos geométricos computacionales , y tales 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 computación con una historia que se remonta a la antigüedad.
La complejidad computacional es fundamental para la geometría computacional, con una 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 de 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 mallas) y visión artificial ( reconstrucción 3D ).
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.