Hoy día 27 de junio de 2011 comienza en la Universidad de Alcalá el XIV Spanish Meeting on Computational Geometry. Este congreso bianual, que concluirá el jueves día 30 de junio, está dedicado en este año 2011 al 60 cumpleaños del profesor Ferrán Hurtado:

Ferrán Hurtado

Como podéis ver en el título del congreso, la temática del mismo es la Geometría Computacional. Bien, ¿y qué es la Geometría Computacional? Pues de eso trata este artículo. Pero no os lo voy a explicar yo, sino una auténtica especialista en este tema.

En la charla ¿Se puede «hacer» matemáticas a través de un blog? que di en la Universidad de Sevilla nuestra querida ClaraGrima me comentó que no había visto nada relacionado con Geometría Computacional, tema en la que ella es una especialista, en Gaussianos. Por ello la invité a escribir una colaboración sobre ello para que todos pudiéramos introducirnos en esta rama de las matemáticas. Y aquí está, en el mejor momento posible, aprovechando el comienzo de este importante congreso de Geometría Computacional. Vamos con ello.

¿Qué es la Geometría Computacional?

¿Qué harías si una mañana te encuentras en tu mesa, tu bandeja de entrada o tu vida la siguiente colección de problemas?

  • Tu primo, Jose, quiere abrir una cadena de tiendas de videojuegos en la región, pero quiere hacerlo, lógicamente, lo mejor posible. Dado que ya existe otra cadena de la competencia, y suponiendo que la gente suele preferir la que está más cerca, porque los precios serán más o menos iguales y los juegos idénticos, Jose te pide que le sitúes sus tiendas para que el área de influencia de las mismas, sea mayor que la de la competencia.

  • Por otra parte, tu suegro está terminando de montar una sala de conferencias en su nuevo hotel y necesita saber dónde colocar la pantalla para que el orador sea visto por el mayor número de asistentes. Eso sí, nada de salas rectangulares ni siquiera con planta poligonal regular, que tu suegro es muy moderno y ha diseñado algo inspirado en esto:

  • Ah, y de parte de tu suegra, que a ver si pasas por la peluquería nueva para colocar los focos nuevos de forma que iluminen la sala lo mejor posible, con el menor número de focos, que los que sobren se los llevará para la playa.
  • En otro mensaje, tienes los datos que te manda un colega tuyo, topógrafo y romántico, que ha estado midiendo en la sierra de su pueblo el entorno de la casa de sus abuelos, porque quiere que un arquitecto le diseñe la cubierta de su nuevo chalet en la playa, imitando la orografía de ese paisaje de infancia:

  • Te llama tu madre y te dice que tu prima la que trabaja en la Diputación quiere que le digas dónde colocar el Centro de Salud nuevo de la comarca, para que todos los usuarios estén lo más cerca posible. Y que qué trabajo te cuesta, si a la cuñada de su peor enemiga, Rosa, le dijiste donde colocar la granja de pollos para no molestar a nadie y todo el mundo está contentísimo con la ubicación.
  • Una ex pareja con la que tienes buenas relaciones de amistad, te pide que le ayudes con un trabajo de fotografía, calculando el menor rectángulo que encuadra a una serie de objetos que ha fotografiado y con los que quiere hacer un mosaico-collage, o almazuela:

  • El Decano de tu ex-facultad te escribe para que le ayudes con la ubicación de unos repetidores de wifi en el centro, de forma que todo el edificio tenga asegurada la cobertura inalámbrica al menos por uno de los repetidores, pero de forma que el decanato esté cubierto por, al menos, 3 de los repetidores, por si se cayera uno de ellos. Eso sí, colocando los menos repetidores posibles, que está la cosa muy achuchá.
  • Sí, tu actual pareja trabaja en AENA y te pide, con la nariz arrugadita, que ubiques las escaleras y cintas mecánicas en la nueva terminal de forma que minimicen el tiempo de desplazamiento de los usuarios, que van los pobres luego asfixiaditos corriendo por las cintas mecánicas:

Puede que ante tal panorama, uno pudiese tener la tentación de escapar en busca de aquel famoso Curro que se fue creo que al Caribe, pero, a la vuelta, seguiríamos con los mismos problemas sobre la mesa. Porque el Decano, tu ex y, puede que hasta tu actual pareja, buscaran otra alternativa, pero ni tu suegra ni tu madre iban a flaquear en el intento.

Entonces, para resolver de la forma más eficiente y rápida posible esta lista de tareas, lo más recomendable es buscar (y encontrar, claro) alguien con conocimientos de Geometría Computacional. Evidentemente, cada uno de estos problemas concretos se puede resolver a mano sin necesidad de implicar a un matemático en tu vida, pero las herramientas que proporcionan la Geometría Computacional para éstos y otros problemas servirán en estas situaciones y en otras diferentes.

Pero, ¿qué es la Geometría Computacional (GC) o Geometría Algorítmica?

Se trata, como dicen algunos autores, de la conjunción de la Geometría Clásica con la Informática. Partiendo de la abstracción de problemas de otras áreas (tales como diseño asistido, robótica, CAD/CAM, bases de datos o incluso biología molecular), la GC trata de desarrollar herramientas y técnicas para resolver problemas de naturaleza, principalmente, geométrica, con especial énfasis en el diseño eficiente de algoritmos y estructura de datos.

Fue bautizada en 1975 por Michael Shamos al acuñar este término por primera vez en el título de su tesis doctoral, dirigida por Franco Preparata. El libro de ambos, [Preparata], por cierto, es para muchos de los que nos dedicamos a esto uno de nuestros manuales de cabecera. No obstante, hay publicados trabajos enmarcados dentro del área muy anteriores, sólo que no se les había catalogado aún.

Para explicar de forma más gráfica cómo respira la GC, vamos a ver cómo es el camino que va desde la matemática continua abstracta al diseño de un algoritmo capaz de resolver el problema con nuestra máquina: el ordenador. Para ello, vamos a plantear un problema: el cálculo de la envolvente convexa de un conjunto finito de puntos en el plano.

Un conjunto en el plano es convexo si contiene al segmento que une a cualquier pareja de puntos contenidos en él (concepto del que ya se ha hablado por aquí):

Dado un conjunto P de puntos en el plano, definimos la envolvente convexa de P, y la llamamos EC(P), como el menor conjunto convexo que lo contiene:

Se trata, por lo tanto, de, dado un conjunto de N puntos P_i=(x_i,y_i), con i=1, \ldots ,N, enseñar al ordenador a calcular la envolvente convexa, como la vemos en la figura anterior.

Evidentemente, la definición no nos sirve para el diseño del algoritmo. No podemos pensar en calcular todos los conjuntos convexos que contienen a P y quedarnos con el más pequeño por varias razones. La primera es ¡que hay infinitos! Por lo tanto, el primer paso será acabar con esa infinitud, esto es, tratar de utilizar otras aproximaciones que nos den, al menos, la posibilidad de elegir entre un número finito de conjuntos convexos.

Usemos nuestra intuición geométrica. Si pensamos que sobre cada punto de P clavamos (no del todo) un clavo, la frontera de la EC(P) sería la forma que adoptaría una goma elástica al soltarla alrededor de ellos, ¿verdad? Pues bien, ya tenemos una primera idea para acabar con la infinitud inicial: la EC(P) (concretamente, su frontera, pero vamos a abusar un poco del lenguaje) será un polígono convexo y simple (cada dos lados o se cortan en un vértice o no se cortan) cuyos vértices son puntos de P. Habría que determinar:

  1. ¿Cuáles son los puntos de P que forman parte de EC(P)?
  2. ¿En qué orden están para definir el polígono? (Un conjunto de k puntos puede definir más de un polígono simple)

¡Tenemos un algoritmo!

Algoritmo 1:

  1. Considerar todos los posibles subconjuntos de P.
  2. Para cada subconjunto, considerar todos los posibles polígonos cerrados, simples y convexos que se pueden construir usando los puntos de dichos subconjuntos como vértices.
  3. Para cada uno de esos polígonos, comprobar si contienen al resto de los puntos de P en su interior.

¿Podemos darnos por satisfecho? Pues no, porque para un conjunto de N puntos hay 2^N posibles subconjuntos y eso es demasiado. A ver, 10^{100} es finito, sí, pero no desde el punto de vista informático: un FLOPS de 1 Giga sólo hace 10^{20} operaciones ¡en un siglo!

Un pequeño paréntesis para hablar un poco de eficiencia de los algoritmos.

Habitualmente, en Geometría Computacional, se usa para el análisis de eficiencia el modelo teórico RAM real. En este modelo, cada número real se almacena en una unidad de memoria, y las siguientes operaciones pueden realizarse con coste unitario:

  • (1) acceso a la memoria;
  • (2) operaciones aritméticas básicas (+, -, ×, /);
  • (3) comparación de dos números reales (<, [latex]\le[/latex], =, [latex]\ne[/latex], [latex]\ge[/latex], >);
  • (4) (ocasionalmente) raíces enésimas, funciones trigonométricas, la exponencial y el logaritmo.

El Algoritmo 1, analizado según este modelo, tiene un coste superior, en el peor de los casos, a 2^N (escrito en notación algorítmica es de orden O(2^N)) y eso, francamente, no sirve pa ná algorítmicamente hablando. Si la unidad de medida es la millonésima de segundo (= 1 microsegundo = 1 µs) y se tienen 60 puntos, un algoritmo de orden 2^N tardaría ¡366 siglos! Parece que tendremos que esforzarnos un poco más, ¿no?

Sigamos usando nuestra intuición geométrica:

Las aristas de EC(P) son segmentos que unen parejas de puntos de P entre sí y con la propiedad de que la recta que contiene a esos segmentos dejan a los N-2 puntos restantes en uno de los 2 semiplanos que ésta define. Ea, pues ya tenemos otro algoritmo.

Algoritmo 2:

  • Considerar todas las posibles parejas de puntos de P (hay del orden de O(N^2))
  • Para cada pareja, comprobar si los N-2 puntos restantes de P están todos en el mismo semiplano de los dos que define la recta que pasa por dicha pareja de puntos.

Con este algoritmo, identificar la EC(P) arista a arista, nos tomaría un tiempo de N^3. ¿Podemos mejorarlo? ¿No está bien ya? Pues bueno, pasar de 2^N a N^3 está francamente bien, pero hay que intentar bajar al máximo el tiempo de ejecución de los algoritmos, porque un algoritmo con coste de N^3 con 10000 datos tarda más de 11 días en ejecutarse y uno N^2 sólo tardaría 1 minuto y 40 segundos.

Pues venga, vamos a explorar aún más la geometría de este problema.

En 1973, en un trabajo de Jarvis, se presenta un algoritmo de cálculo para la EC(P) con coste computacional, en el peor caso, de N^2. Este algoritmo se conoce como la Marcha de Jarvis o algoritmo de Gift Wrapping (envoltura de regalos).

Algoritmo 3: Marcha de Jarvis

  • Calcular un punto que sepamos seguro que está en la envolvente convexa, por ejemplo, el de coordenada y más baja (esto nos tomará tiempo O(N), calcular el mínimo de un conjunto de N puntos). Lo llamamos P_0.
  • Calcular el ángulo que forman los N-1 puntos restantes con él y con la horizontal, y elegir el más pequeño (tardamos tiempo O(N) otra vez). Ese punto será P_1:

  • Seguiríamos este procedimiento en cada nuevo punto encontrado, hasta volver a P_0. Para P_2:

    Y para P_3:

Puesto que pudiera ocurrir que todos los puntos de P formaran parte de la EC(P) (el peor de los casos), tendríamos que calcular los N-1 ángulos N veces, arrastrándonos a un coste en el peor de los casos de O(N^2). Qué bien, ¿no?

¿Se puede mejorar? ¿Me estoy poniendo pesada?

Bueno, es que es bastante relevante lo de reducir al máximo la complejidad de los algoritmos, porque si un O(N^2) tarda 1 minuto y 40 segundos en 10000 puntos, uno un pelín más barato, digamos un O(Nlog(N)) tardaría para 10000 datos 0,04 segundos, y oye, en los tiempos que corren…

Vamos a intentarlo, ¿no? ¡Que no decaiga!
Haberlos, haylos, y muchos, algoritmos que calculan la EC(P) de N puntos en tiempo O(Nlog(N)). El algoritmo de Graham para el cálculo de la EC(P) es uno de los más conocidos, a mí me gusta mucho.

¿Os lo cuento?

Algoritmo 4: Scan de Graham

  • Calcular un punto de la EC(P), por ejemplo, el más bajo, P_0.
  • Ordenar angularmente los N-1 restantes respecto de P_0 (esto nos cuesta O(Nlog(N)), es el mejor tiempo posible para ordenar N números).
  • Comenzando en P_0 y siguiendo la lista ordenada, comprobamos cada 3 puntos si el giro por ellos es horario o antihorario, y en función de ese signo decidimos si borrar el central o no (esto nos ocupa del orden de O(N) comprobaciones).

Vamos a verlo con un ejemplo gráfico:

Elegido P_0, etiquetamos los demás puntos siguiendo el orden angular, tal y como se ve en la figura anterior. A continuación, comprobamos el sentido del giro de la primera terna (P_0 ,P_1,P_2):

Como el giro es positivo, antihorario, avanzamos y consideramos la siguiente terna (P_1,P_2,P_3)

Otra vez el giro es positivo, seguimos con (P_2,P_3,P_4):

Cuando el giro es negativo, como en la figura anterior, eliminamos el punto central de la terna, que por tanto no formará parte de la envolvente convexa, retrocedemos un punto y volvemos a empezar. Ahora (P_1,P_2,P_4):

Y continuamos de la misma forma hasta llegar otra vez a P_0. En la siguiente animación tenéis la traza completa de este ejemplo en particular:

Al final de esta entrada os dejo unas referencia para aquellos que lo quieran ver en detalle.

Recordemos que comenzamos con infinitos conjuntos que manejar y hemos conseguido un algoritmo O(Nlog(N)) ¿Seguimos o paramos? ¿Cómo decidimos si seguir mejorando la complejidad o parar? Pues depende. A veces paramos porque no nos sale nada más, y en otras ocasiones, como en este caso, porque hemos llegado al óptimo. No podremos conseguir nada mejor.

¿Qué cómo lo sé? Pues porque calcular la EC(P) de un conjunto de N puntos en el plano es equivalente a ordenar N números y es sabido que esto último no se puede hacer en menos tiempo.

Espero que al llegar a esta línea ya hayáis percibido el olor y el sabor de la Geometría Computacional en una primera aproximación. Pero no olvidemos los problemas del principio, que fueron los que nos trajeron aquí. Vamos a ir apagando fuegos:

  • A tu primo José le dices que estudie los diagramas de Voronoi. El diagrama de Voronoi de un conjunto de puntos asigna a cada uno de ellos la región más cercana del plano.
  • A tus suegros, habría que ilustrarlos un poco en la rama de la Geometría Computacional que se ocupa de problemas de Galería de Arte. Aquí podéis ver un ejemplo sencillo de vigilancia e iluminación.
  • Para el topógrafo romántico, te recomiendo echarle un vistazo a la triangulación de Delaunay que optimiza los ángulos de los triángulos, proporcionando una representación lo más parecida posible a la real.
  • A tu prima, la de la Diputación, dile que coloque el Centro de Salud en el centro del menor círculo que recubra a los usuarios. Para ello habrá que explicarle qué es el diámetro y hablarle del Diagrama de Voronoi de los puntos más alejados.
  • Sí, fue más fácil ubicar la granja de pollos para Rosa, porque cuando el servicio es indeseable, se trata de colocarlo en el centro del mayor círculo vacío, y ése está centrado en un vértice del Diagrama de Voronoi.
  • A tu ex-pareja háblale del mínimo rectángulo recubridor, le mandas la referencia o te la estudias y se la explicas tomando unas tapas, eso depende de lo que marques la x al decir ex.
  • Al Decano los pones en contacto con tus suegros para que le expliquen técnicas para vigilancia e iluminación, y cuando esté al día que se ponga con los nuevos trabajos de la disciplina de ubicación de routers.
  • En cuanto a tu pareja actual, te recomiendo que le des algunas referencias sobre diagramas de Voronoi dinámicos, que incluyen escaleras y cintas mecánicas.

No sé si hace falta decir a estas alturas de la entrada que me fascina la Geometría Computacional por muchas razones, pero sobre todo por el reto que supone someter mi razonamiento clásico y continuo, aprendido desde bebé en la Facultad de Matemáticas, a la dura prueba de modelar y discretizar problemas para que puedan ser resueltos por la máquina.

Como se comenta al principio de esta entrada, este año se celebra el XIV Spanish Meeting on Computational Geometry en la Universidad de Alcalá. Os lo recomiendo porque entre otros muchos grandes de la Geometría Computacional estarán Erick Demaine, gran matemático y divulgador, y el magnífico Jin Akiyama, uno de los personajes más conocidos de Japón por hacer matemáticas en TV, al que además tengo la suerte de conocer en persona (y del que nuestro querido twalmar nos habló hace un tiempo)

Y ya en plan Francisco Umbral, D.E.P., os dejo la referencia de nuestro libro Computational Geometry on Surfaces, donde se plantean y se resuelven algunos de los problemas clásicos de la Geometría Computacional pero para puntos localizados, no en el plano ni en el espacio tridemensional, sino en las superficies más simples: cilindro, toro y esfera.

Y ya termino, ahora de verdad, agradeciendo a Gaussianos la oportunidad de asomarme por su ventana para hablar de Geometría Computacional, lo que es un honor sin duda para mí que soy una novata en el mundo de los blogs. Gracias ^DiAmOnD^, te debo una soda ;).

^DiAmOnD^: Gracias a ti Clara, por introducirnos en tu mundo, la Geometría Computacional, con este magnífico artículo y por darme la oportunidad de publicarlo en Gaussianos. Acepto esa soda :).

Bibliografía:

  1. J. O’Rourke, Computational Geometry in C Second Edition, Cambridge University Press, 1998.
  2. Mark de Berg, et al., Computational Geometry: Algorithms and Applications, Springer Verlag, 1997.
  3. F. P. Preparata and M. I. Shamos, Computational Geometry, Springer-Verlag, 1985.
  4. J. O’Rourke, Art Gallery Theorems and Algorithms, Oxford University Press, 1987.
  5. J. E. Goodman and J. O’Rourke, Eds., Handbook of Discrete and Computational Geometry, CRC Press, Boca Raton, 1997.

Actualmente, las publicaciones más relevantes en Geometría Computacional son:

Esta entrada es mi primera colaboración a la Edición 2.5 del Carnaval de Matemáticas, que en esta ocasión organiza Mago Moebius.

Print Friendly, PDF & Email
5 2 votes
Article Rating

¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉


Comparte: