thumb|Cilindro renderizado mediante un programa de ordenador. La geometría computacional es una rama de las ciencias de la computación dedicada al estudio de algoritmos que pueden ser expresados en términos de la geometría. Algunos de los problemas puramente geométricos surgen del propio estudio de dichos algoritmos, y este tipo de problemas también se considera parte de la geometría computacional. También se considera una rama gráfica del ordenador. Introducción Una parte significativa del crecimiento que la Matemática Discreta, como un todo, ha experimentado en los últimos años, ha consistido en un desarrollo sustancial de la Geometría Discreta. Esto ha sido impulsado, en parte, por el desarrollo de ordenadores cada vez más potentes, y por la reciente explosión de actividad en el campo relativamente joven de la geometría computacional.
¿Y qué es la Geometría Computacional? En pocas palabras, es el arte de resolver problemas conceptualmente sencillos usando los menos recursos posibles y empleando el mínimo tiempo posible. La Geometría Computacional surgió a finales de los 70s del área de diseño y análisis de algoritmos. La mayoría de los estudios algorítmicos que abordaban estos problemas han ido apareciendo a lo largo de los últimos 150 años, aunque sobre todo en los últimos treinta. De todas formas, sólo muy recientemente han sido realizados estudios sistemáticos de algoritmos geométricos y cada día más investigadores se sienten atraídos por la disciplina que fue bautizada en 1975 por Shamos.
Hasta hace poco, Geometría Computacional se refería al diseño y análisis de algoritmos geométricos, pero en los últimos años ha ampliado su campo, y ahora también incluye el estudio de problemas geométricos desde un punto de vista computacional, incluyendo también convexidad computacional, topología computacional y complejidad combinatorial de disposiciones de poliedros.
En los últimos años ha aumentado el número de áreas en las que se aplican los resultados de esta disciplina. Entre las mismas se incluyen la ingeniería, cristalografía, diseño asistido por computador, sistemas de posicionamiento global, robótica, sistemas de detección de errores, modelado geométrico, gráficos por ordenador, optimización combinatorial, visión por ordenador, reconocimiento de patrones y modelado sólido.
Descripción Es una disciplina constructiva, de carácter abstracto, que utiliza técnicas de la geometría clásica, la topología, la teoría de grafos, la teoría de conjuntos y el álgebra lineal. La geometría computacional es independiente de la tecnología de las máquinas de computación, si bien pone atención en proporcionar soluciones que se comporten de forma computacionalmente robusta.
La complejidad computacional es fundamental para la geometría computacional, con un enorme significado práctico si los algoritmos se usan en grandes conjuntos de datos que contienen decenas o cientos de millones de puntos. Para tales conjuntos, la diferencia entre O(n^2) y O(n logn) puede ser la diferencia entre días o segundos de computación.
El principal impulso para el desarrollo de la geometría computacional se lo dio el avance de la computación gráfica y el diseño asistido por ordenador (CAD/CAM), que hacen uso intensivo de las técnicas de esta disciplina. Otras aplicaciones importantes de la geometría computacional incluyen la robótica (planificación de movimientos y problemas de visualización), los sistemas de información geográfica (SIG) (localización y búsqueda geométrica, planificación de rutas), diseño de circuitos integrados (diseño geométrico y verifición de CI), ingeniería asistida por computadora (CAE) (programación de máquinas controladas numéricamente).
Las principales ramas de la geometría computacional son: Geometría computacional combinatoria, también llamada geometría algorítmica, que trata de objetos geométricos como entidades discretas. Un libro sobre el tema por Preparata y Shamos fecha la primera utilización del término "geometría computacional" en este sentido en 1975. Geometría computacional numérica, que trata principalmente con la representación de objetos del mundo real en la forma adecuada para ser almacenada en un ordenador. Esta rama puede ser vista como un desarrollo de la geometría descriptiva y es a menudo considerada como una rama de los gráficos por ordenador o CAD. El término "geometría computacional", en este sentido ha estado en uso desde 1971.
Complejidad algorítmica Frecuentemente se tiene que un mismo problema puede resolverse mediante distintos algoritmos y es preciso establecer criterios que nos permita decidir cuál es mejor. En general se atiende a razones de economía en cuanto al número de operaciones que necesita el algoritmo para resolver el problema.
La complejidad de un algoritmo no es sino una medida del coste que supone su ejecución tanto en tiempo (o número de operaciones "elementales" que ha de realizar) como en espacio (o unidades de memoria requeridas para almacenar y manipular los datos a lo largo de la ejecución) y vendrá dada en función del número de datos de entrada.
El estudio de la complejidad de un algoritmo puede llevarse a cabo principalmente bajo dos puntos de vista:
Complejidad en el peor de los casos. Complejidad en media (o esperada).
La primera consiste en medir la complejidad del algoritmo atendiendo a su ejecución cuando trata los datos del problema en el caso más desfavorable, entendiéndose por desfavorable el más costoso.
La segunda consiste en medir la complejidad haciendo un promedio entre todos los casos (favorables y no favorables) atendiendo a la probabilidad de que aparezcan como entrada. Para ello se supone que los datos de entrada vienen dados conforme a cierta distribución de probabilidad y se estudia cuál es el tiempo esperado de ejecución.
Si n es el tamaño del conjunto de datos de entrada de un determinado algoritmo, sus complejidades en tiempo y en espacio son funciones positivas de n y, en cuanto a su análisis, se está especialmente interesado en su comportamiento asintótico, es decir, en saber cómo se comportan para valores grandes de n.
La notación que utilizaremos en el estudio asintótico de estas funciones es la estándar propuesta por Knuth:
Si f(n) y g(n) dos funciones positivas se dirá que
1. "f es o grande de g" y se notará f(n) = O(g(n)) si existen una constante C > O y un número natural n0 > O tales que
f(n) menor Cg(n) para todo n > n0
2. "f es omega de g" y se notará f(n) Q(g(n)) si g(n) = O(f(n))
3. "f es theta de g" y se notará f(n) = O(g(n)) si f(n) = O(g(n)) y f(n) = Q(g(n)).
Geometría computacional combinatoria thumb|Triangulación de un polígono. 1. Abanico. 2. Mínimo peso 3. Delaunay thumb|Cálculo del cierre convexo de un conjunto de puntos por el Método de Graham. thumb|Triangulación de Delaunay y Diagrama de Voronoi de un conjunto de puntos. El objetivo principal de la geometría computacional combinatoria es el desarrollo de algoritmos y estructuras de datos eficientes para resolver problemas basado en términos de objetos geométricos: puntos, segmentos, polígonos, poliedros, etc.
Algunos de estos problemas parecen tan simples que no fueron considerados como tal hasta la llegada de los ordenadores. Por ejemplo, la determinación del cierre convexo de un conjunto de puntos puede ser realizada de forma intuitiva sobre un papel utilizando una regla, pero no es tan evidente dar las instrucciones a un ordenador para que lo resuelva. Otro problema, el de encontrar el par de puntos más cercanos puede ser implementado de forma sencilla mediante una búsqueda por fuerza bruta, calculando la distancia entre las n(n-1)/2 combinaciones posibles de pares de puntos y eligiendo la menor, pero esta solución no es aplicable para conjuntos con un elevado número de puntos.
Algunos problemas clásicos A continuación se enumeran algunos problemas clásicos que han sido estudiados en el campo de la Geometría computacional combinatoria:
Cierre convexo: Dado un conjunto de puntos, encontrar el polígono convexo de menor área que los contenga. Triangulación de un polígono: Descomponer un polígono en una serie de triángulos que lo recubran. Problema del par de puntos más cercanos: Dado un conjunto de puntos, encontrar el par de puntos más próximos entre sí. Diámetro de un conjunto de puntos: Dado un conjunto de puntos, encontrar el par de puntos más alejados entre sí. Problema del mayor círculo vacío: Dado un conjunto de puntos, encontrar el mayor círculo con centro dentro del cierre convexo y que no contenga ningún punto. Intersección de segmentos de recta: Dado un conjunto de segmentos en el plano, encontrar todos los puntos de intersección en segmentos. Operaciones booleanas sobre polígonos: Calcular de forma eficiente uniones/intersecciones entre polígonos. Problema de la galería de arte: Determinar el mínimo número de puntos de un polígono que son suficientes para ver a todos los restantes. Búsqueda de rango: Dado un conjunto de puntos, encontrar aquellos en el interior de una figura geométrica dada.
Problemas dinámicos Otra gran clase es la de los problemas dinámicos, en la cual el objetivo es encontrar un algoritmo eficiente para encontrar la solución repetidamente tras cada modificación incremental de los datos de entrada (adición o supresión de los elementos geométricos de entrada). Los algoritmos para los problemas de este tipo típicamente supone estructuras dinámicas de datos. Cualquiera de los problemas de geometría computacional puede ser convertido en uno dinámico, con el coste de incrementar el tiempo del proceso. Por ejemplo, el problema de la búsqueda de rango provisto de adición y/o supresión de los puntos. El problema de la Envolvente convexa dinámica es mantener un seguimiento de la envolvente convexa; por ejemplo, para los conjuntos de datos que cambian dinámicamente, o mientras que los puntos de entrada son insertados o suprimidos. La complejidad computacional para esta clase de problemas se estima mediante: El tiempo y espacio requeridos para construir la estructura de datos que se va a buscar. El tiempo y 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 extra de espacio) para responder la consulta.
Sistemas de Geometría Dinámica (SGD/DGS) el término sistema aludiendo a un conjunto integrado de componentes como principal elemento un núcleo o kernel de geometría dinámica computacional con interfaz gráfica de usuario (GUI) y en algunos casos incluye scripts para automatizar procedimientos como lo realiza la aplicación GeoGebra
Variantes Algunos problemas pueden ser tratados bajo el punto de vista estático y dinámico dependiendo del contexto. Por ejemplo, considerando el siguiente problema: Punto en un polígono: Decide si un punto está dentro o fuera de un polígono dado. Muchas de las puestas en práctica de este problema dan resultados con un único intento, esto es, perteneciendo a la primera clase. Por ejemplo, en muchas aplicaciones de la computación gráfica, un problema común es encontrar en qué área de la pantalla se hace clic con el cursor. 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 el punto es la posición de un avión, y el problema es determinar si el avión ha violado la frontera. Finalmente, el ejemplo anteriormente mencionado de la computación gráfica, en aplicaciones CAD los datos de entrada que cambian son usualmente almacenados en estructuras de datos dinámicas, lo cual puede ser explotado para agilizar las consultas de punto en un polígono.