Geometría computacional
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.
Las principales ramas de la geometría computacional son: 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.
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.
Sin embargo, en algunas aplicaciones el polígono en cuestión es invariante, mientras que el punto representa una consulta.
El significado del término computación se ha expandido notoriamente desde la introducción de los ordenadores, hará ahora unos cincuenta años.
La segunda, propiciada por necesidades más comerciales y administrativas, incorporaba largas listas de datos (por ejemplo alfabéticos), con vistas a cómo leer, almacenar, modificar, seleccionar, e imprimir esos datos.
La Geometría Computacional ha emergido, ciertamente, por la necesidad de dar respuesta a esta nueva y creciente demanda.
Se podría decir que las aplicaciones van a preceder la disciplina, y ahora que ésta tiene ya un núcleo teórico sólidamente constituido, como sus vertientes prácticas corresponden a tecnología de máxima vanguardia, la demanda de resultados continúa con la misma fuerza y exigencia que al principio.
Se espera que la Geometría Computacional haga grandes mejoras a los algoritmos estándar usados en gráficos por ordenador.
Una cuestión muy importante en informática gráfica es la representación realista de escenas complejas.
Los resultados de estas investigaciones han dado nuevas aplicaciones en informática gráfica.
Dicho algoritmo corre en tiempo 0(n2) donde n es el número de lados del polígono.
Utilizando técnicas desarrolladas para el diseño de algoritmos en Geometría Computacional, ElGindy y Avis consiguieron un algoritmo para este problema que corre en tiempo (óptimo) 0(n), cuando n es grande esto supone una mejora sustancial en la velocidad de ejecución.
Una de las técnicas utilizadas en la fabricación industrial de objetos consiste en utilizar moldes en los que se inyectan ciertos materiales líquidos que al solidificar dan lugar al objeto requerido con la forma imprimida por el molde.
Durante la inyección del líquido, el molde es colocado en una posición favorable de manera que no aparezcan defectos en la superficie tales como burbujas de aire y se garantice un llenado completo.
Dos de los problemas que surgen en este contexto son: dado un objeto tridimensional como molde , establecer si existe una orientación que permite el llenado del molde usando sólo un punto de inyección y determinar una orientación que permita el llenado más completo.
Habitualmente en la práctica se sigue un proceso de prueba y error utilizando ciertas técnicas intuitivas.
En el primero, el problema típico involucra un robot, generalmente modelizado como un punto, un disco, o un polígono en dos dimensiones, o bien como un poliedro en tres dimensiones que ha de moverse en el espacio entre una colección de obstáculos.
