matemáticas en acción: Geometría Computacional


Hoy he asistido a una conferencia muy interesante sobre Geometría Computacional, una rama muy práctica de las matemáticas que permite resolver mediante la concepción de algoritmos eficientes muchos problemas geométricos que aparecen en proyectos de ingeniería. La conferencia ha sido impartida por Manuel Abellanas, profesor de una asignatura optativa de Geometría Computacional en la Factultad de Informática de la Universidad Politécnica de Madrid. En dicha asignatura se han desarrollado muchos proyectos que han tenido como resultado programas de demostración, algunos rayando la calidad profesional, entre los cuales se encuentran algunos que el ponente ha utilizado en esta presentación (al final de la presentación nos dio un enlace en donde el ponente ha almacenado los programas concretos que ha utilizado)

La presentación (taller) ha girado entorno a dos objetos matemáticos relacionados entre sí y con la teoría de grafos. El primero es el Diagrama de Voronoi. El segundo es la triangulación de Delone. A partir del planteamiento de varios problemas geométricos se han introducido las estructuras básicas de la geometría computacional que hemos mencionado y la manera algorítmica de resolverlos, que lleva a la solución computacional.

La Geometría computacional se ocupa de resolver problemas geométricos de forma algorítmica. Es decir, busca métodos para obtener las soluciones de forma efectiva. No obstante la efectividad no lo es todo. También hay que tener en cuenta la eficiencia. Normalmente no hay sólo un algoritmo para resolver un problema. Interesa conocer cuál es mejor que los demás. La bondad de los algoritmos se mide en función del tiempo que requieren para llegar a la solución y los recursos que necesitan (espacio de memoria, recursos de computación, número de operaciones que realizan) para llevar a cabo el proceso que describen. Esas medidas de conocen como la complejidad del algoritmo. Se suelen estudiar de forma asintótica cuando el número de elementos del problema tiende a infinito. Los límites de la complejidad de los algoritmos que resuelven un determinado problema se denominan complejidad del problema. Si obtenemos un algoritmo cuya complejidad coincide con la del problema que resuelve, decimos que hemos obtenido un algoritmo óptimo.

El ponente también mencionó que en el mundo real el uso de algoritmos en ocasiones va más allá de la complejidad teórica en tiempo y recursos que tienen asignada. La complejidad de la implementación en líneas de programa y recursos humanos para su programación también se tienen en cuenta. En ocasiones se utilizan algoritmos que no son óptimos pero son sencillos de implementar, son más robustos (menos líneas de código reducen el riesgo de errores) y requieren pocos recursos humanos (y por lo tanto económicos)

Al principio de la conferencia nos pasaron unas hojas con siete problemas planteados que íbamos a ir resolviendo durante la charla, obteniendo los algoritmos previa utilización de los objetos geométricos que nos permitieron discretizar y simplificar el problema de manera que fuera soluble con el menor número de operaciones posible y con un crecimiento lineal del número de operaciones con el incremento del número de datos iniciales del problema.

Voy a poner ahora los tres primeros problemas. El resto los iré completando en los comentarios de este artículo.

PROBLEMA 1: Telefonía móvil

El primer problema geométrico que se planteó fue el de la distribución de estaciones base de telefonía móvil en un espacio bidimensional. Se supone que los usuarios de teléfono móvil están distribuidos de forma uniforme en el espacio bidimensional considerado. La clave del problema es que cada teléfono móvil se conecta por radio con la antena más próxima al lugar donde se encuentra. Cada antena tiene asignada una región del plano a la que presta el servicio. ¿Cómo son esas regiones y como queda descompuesto el plano en función de la posición de la antena que se encarga de la cobertura?

La solución son regiones convexas poligonales alrededor de los puntos donde se encuentran las estaciones base. La estructura de dichas regiones se denomina Diagrama de Voronoi (en honor al matemático ruso, Georgy Voronoi, que los inventó) Para “demostrar” dicha solución el ponente utilizó un programa de Geometría Computacional de libre distribución llamado GeoGebra. Este programa open source permite construir estructuras geométricas y realizar variaciones en dichas estructuras observando los resultados dinámicos en tiempo real (a estos programas se les denomina de Geometría Activa y son muy populares en la enseñanza de la materia)

La solución algorítmica del problema geométrico se basa en encontrar las regiones que dividen el plano a partir de la distancia máxima entre parejas de puntos. La estructura geométrica que determina dichas regiones es la mediatriz. Mediante el programa citado se puso el caso de un punto, dos puntos, tres puntos, … en cada caso se debieron trazar las medianas de cada pareja de puntos presentes. Este es un ejemplo de algoritmo incremental en el que se va procesando según se reciben los datos (i.e los puntos donde se localizan las estaciones base)

A partir del cuarto punto, la estrategia que se usa es ver el punto más cercano a este nuevo punto y empezar a trazar la mediatriz entre esos dos puntos. Se verá que las mediatrices se intersectan entre ellas y definen segmentos. Estos segmentos definen las fronteras de regiones, algunas abiertas y otras cerradas. En cualquier caso son regiones convexas. Las regiones se pueden definir como intersecciones entre los planos. Cuando el número de puntos se incrementa, se forma el Diagrama de Voronoi.

El ponente mostró las cualidades de un programa creado por sus alumnos llamado Depthlone que permite calcular de forma automática los diagramas de voronoi colocando los puntos de forma aleatoria y importando los puntos de archivos externos (por ejemplo de un mapa de Cantabria en el que los puntos eran los núcleos de población)

NOTA: Muchos de los programas están construidos a partir de una librería llamada CGAL, escrita en C++, y que es el resultado de un proyecto internacional.

Los Diagramas de Voronoi pueden generalizarse y construirse alrededor de otros objetos que no tienen porque ser puntos (el ponente mostró con ayuda del programa como se podía hacer con nubes de puntos en forma circular o cuadrada, que podían ser una representación discreta de objetos más complejos; el secreto está en eliminar los segmentos de las regiones que pertenecen a la misma nube de puntos), con una definición de distancia diferente a la euclidiana, etc.

PROBLEMA 2: Buscando el camino más seguro

El segundo problema que se abordó fue el de un corredor olímpico con una antorcha que debe ir desde un punto A a un punto B en los extremos de un rectángulo en el cual hay distribuidos una serie de puntos que representan escapes de gas. Se pide calcular el camino más seguro.

El camino más seguro será aquel que pase lo más alejado posible de cualquiera de los puntos que se pueda encontrar por el camino. Este problema de juguete es un ejemplo de un problema real que se puede presentar por ejemplo si el camino es el trazado de un oleoducto y los puntos representan zonas pobladas.

El camino seguro tiene que maximizar la mínima distancia hasta los puntos en cualquiera de los puntos de su trayectoria. El ponente nos avanzó que se puede demostrar matemáticamente que la solución tiene que ser poligonal, es decir, que el camino será una sucesión de segmentos rectilíneos. La solución propuesta, con ayuda de un programa de ordenador realizado por sus alumnos, es hacer crecer círculos alrededor de los puntos (al mismo tiempo desde todos los puntos) representado las zonas seguras por las que no puede pasar el camino. A medida que crecen los círculos se ve que el camino se restringe y se hace más poligonal. Cuando los círculos se juntan o se topan con el límite del rectángulo se forman segmentos de línea que son las mediatrices de los puntos sobre los que se han hecho crecer los círculos. En el límite los segmentos forman un diagrama de voronoi y un conjunto de ellos representan cada uno de los caminos posibles que se pueden tomar.

Una optimización posterior consiste en encontrar el camino más corto que transita por los segmentos. Si consideramos los segmentos como aristas y las intersecciones como nodos tenemos un grafo por el que podemos utilizar técnicas conocidas para encontrar ese camino mínimo!

Se puede concluir que al principio, cuando teníamos solamente los puntos teníamos infinitos posibles caminos en un continuo. Al hacer crecer los círculos y formar el diagrama de Voronoi se discretiza el problema y se convierte el problema continuo en un problema discreto con un número finito de caminos formados por las combinaciones de los segmentos que forman las fronteras entre las regiones del diagrama de Voronoi. La discretización de un problema facilita su formalización en un algoritmo!

PROBLEMA 3: Control aéreo

Una variación del problema anterior es el de un avión que sigue una (teórica) trayectoria rectilínea alrededor de la cual se encuentran desperdigadas torres de control. El avión debe mantenerse en contacto con la torre de control más próxima en todo momento. Hay que descomponer la trayectoria según la torre de control con la que se debe conectar en cada punto.

Aquí la solución pasa por dividir el tramo rectilíneo que recorre el avión sobre el plano geométrico en función de las regiones de un Diagrama de Voronoi creado a partir de los puntos que representan a las torres de control.

Si no utilizamos las regiones del Diagrama de Voronoi y consideramos solamente las mediatrices entre los puntos (torres de control) y las intersecciones de las mismas con la trayectoria del avión tenemos un problema de explosión combinatoria. El número de mediatrices que se requieren es de “n sobre 2” (número combinatorio) Las operaciones necesarias para obtener las mediatrices mediante un algoritmo va aumentar con el número de puntos en o(n^2) (utilizando la notación de cálculo asintótico de complejidad de algoritmos) al que hay que sumar el de las intersecciones.

Disponiendo de un buen algoritmo de obtención de Diagramas de Voronoi, y lo hay con una complejidad o(nlogn), obtendremos un número de aristas que crece de forma lineal (es una función lineal) con el número de puntos (en vez de crecer de forma cuadrática) Esto supone un importante ahorro de operaciones. Es por tanto una solución más eficiente.

En la práctica la reducción de la complejidad de los algoritmos está matizada por la complejidad de su implementación.

3 comentarios en “matemáticas en acción: Geometría Computacional

  1. PROBLEMA 4. Control Aereo con M aviones

    El siguiente problema es una generalización del problema anterior con m aviones que atraviesan el plano y n torres de control. Se suponen trayectorias rectilíneas y velocidad constante. Cada trayectoria está definida por los puntos inicial y final y los instantes en los que el avión correspondiente se encuentra en ellos. Hay que determinar qué torre de control tiene que controlar al mismo tiempo el mayor número de aviones.

    Lo primero que nos podemos preguntar es si podemos utilizar el algoritmo del problema anterior para un avión m veces:

    (1) Hallar el Diagrama de Voronoi de las torres de control o(nlogn)

    (2) Para cada una de las Regiones de Voronoi se calculan los segmentos que la atraviesan (cada uno representando un avión con punto inicial, punto final e instante de entrada en la región e instante de salida calculado a partir de su velocidad constante)

    (3) Para cada una de las parejas de instantes de tiempo obtenidas en cada región se hace una ordenación previa de los segmentos y se obtienen los solapamientos de dichos segmentos (m veces, función lineal)

    La región con el mayor número de solapamientos es la región que buscamos.

    La estrategia que hemos seguido aquí es la reducción de la complejidad convirtiendo un problema discreto bidimensional, en uno unidimensional (intervalos sobre la recta R)

    PROBLEMA 5. Redes de Sensores

    Se conocen las posiciones de n sensores que se comunican por radio con todos aquellos que se encuentran en su radio de cobertura. Todos tienen el mismo alcance. Hallar el alcance mínimo que pueden tener para que la red formada por ellos sea conexa.

    Aquí tenemos una serie de puntos que representan los sensores distribuidos por el plano. Estos puntos se deben conectar entre sí mediante arcos o aristas formando un grafo conexo es decir, en el que desde cualquier nodo exista un camino para ir a cualquiera de los demás de la red. Se garantiza de esta manera que no van a haber islas de sensores desconectadas.

    La solución se puede obtener con una técnica geométrica llamada triangulación de Deloné (en honor al matemático ruso, Boris Delaunay, que la inventó) De lo que hay que darse cuenta es que el grafo resultante de las aristas del Diagrama de Voronoi y el grafo resultante de los arcos de la triangulación de deloné son dos grafos equivalentes (técnicamente son dos grafos isomorfos), es decir, definen el mismo objeto matemático, representan lo mismo. Las intersecciones de las aristas del Diagrama de Voronoi marcan los circuncentros de los triángulos que forman los arcos de Deloné.

    La solución pasa entonces por obtener en primer lugar el Diagrama de Voronoi de la distribución de sensores o(nlogn) y a partir de ahí obtener los arcos de Deloné que unen a los sensores que están más cerca unos de otros, empezando por los que están más cerca y aumentado esa distancia mínima hasta que se forma el grafo conexo (operaciones o(n)) Ordenando de menor a mayor los arcos, el arco mayor es la solución del problema.

    El ponente demostró la solución con ayuda del programa Vorexpand.

  2. PROBLEMA 6. Recuperar la Curva.

    Se trata de averiguar si dados una serie de puntos discretos de una curva arbitraria es posible recuperar la curva original a la que pertenecen.

    La respuesta es afirmativa (siempre que se den una serie de condiciones, claro) La técnica que se utiliza se llama Crust skeleton.

    Sigue más o menos los primeros pasos del algoritmo de solución del problema anterior: diagrama de voronoi, triangulación de deloné y aplicación de un test a las aristas de ambos para ver cuáles se eliminan y cuáles se quedan. La figura geométrica que resulta es un conjunto de aristas llamado esqueleto que determina cómo es la forma de la curva que lo envuelve. Técnicamente es una estructura unidimensional que define la estructura de la curva topológica.

    El ponente mostró un programa de los diseñados por sus alumnos en sus prácticas de la asignatura que reconstruye las curvas utilizando el algoritmo descrito. Se pudo ver como la condición de cercanía de los puntos es clave y cómo “puntos de ruido” excesivamente cercanos pueden provocar la aparición de artefactos que no forman parte de la imagen que se desea obtener.

    Este es el último problema que se trató en la conferencia (que no era el último de los que estaban planteados inicialmente) No obstante yo he echado un vistazo también al último:

    PROBLEMA 7. Mis adorables vecinos

    Conocidas las posiciones de los n vecinos de una región de Laponia, calcular el alcance mínimo que deben tener sus transmisiones de radio para que todos ellos puedan conactar con algún vecino para pedir socorro en caso de emergencia. ¿Qué alcance deberían tener si se quiere que cualquier vecino hable con todos los demás?

    Se supone que los vecinos están agrupados en clusters de puntos formando diferentes figuras lineales (no nubes de puntos) distribuidas por el plano.

    Mi suposición es que este problema es muy similar al de las redes de sensores en su primera pregunta y muy similar al de recuperar una curva a partir de sus puntos en la segunda pregunta (y también al de la red de sensores en el sentido de formar un grafo conexo con todos los puntos ya que eso garantiza que cualquier vecino se puede comunicar con cualquier otro …)

  3. NECESITO AYUDA CON UN PROBLEMA Y TIENE QUE SER AHORA EL PRBLEMA DICE :

    EN UN TERRENO RECTANGULO DE 10.50 M DE FRENTE POR 32.20 M DE FONDO SE QUIERE EDIUNA CASA QUE DEJE LIBRE PARA EL JARDIN 7/15 DE SU SUPERFICIE ¿ QUE PARTE DEL TEERRENO OCUPARA LA C ASA?

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s