Manuel Abellanas
13-abril-2000
Resumen
Este ensayo pretende ser un estímulo para interesar al lector por conocer una nueva rama de la Matemática Aplicada: la Geometría Algorítmica. El germen de esta disciplina se encuentra en la Geometría constructiva de Euclides. Su espectacular evolución actual se debe al desarrollo y las aplicaciones de la Informática. En este trabajo se presentan algunos ejemplos ya clásicos a partir de situaciones reales y se sugieren algunos enlaces para introducirse en el área.
Un controlador aéreo debe avisar a los pilotos de dos
aviones si están demasiado próximos para que cambien su ruta.
En su pantalla hay 80 puntos que representan los 80 aviones que en ese
momento sobrevuelan su zona de control. Tiene claro que debe prestar un
interés especial a la pareja de aviones que estén más
próximos entre sí. Sería bueno disponer de un sistema
que le mantenga informado en todo momento de cuál es el par más
próximo de entre los puntos de su pantalla - piensa. En vista de
lo cual decide poner en práctica sus conocimientos de programación
adquiridos durante su licenciatura en Informática. ¿Cómo
hallar el par más próximo en un conjunto de n puntos del
plano? – Muy fácil – piensa. Calculando la distancia entre cada
par de puntos y guardando la menor de todas ellas. Cuando más satisfecho
está del programa que ha desarrollado, y tras comprobar que funciona
correctamente, se da cuenta de que para el número de puntos que
tiene que procesar en la práctica y dado el número de veces
por minuto que tiene que calcular el par más próximo, su
programa no sirve. Es demasiado lento incluso en su potente ordenador de
la consola de control debido al gran número de operaciones que realiza.
Es entonces cuando decide recurrir a su compañero Félix que
estudió Matemáticas. Lo malo es que últimamente anda
ocupado con asuntos sindicales…
El responsable de planificación de un servicio aéreo
de rescate se encuentra decidiendo dónde ubicar la central de helicópteros
de la comarca. Sabe que debe atender a cualquiera de las localidades en
el menor tiempo posible. Dispone de un plano en el que figuran, representados
por n puntos, los n pueblos de la región. ¿Cuál es
realmente su problema? Un problema de Geometría constructiva. Debe
hallar el menor círculo que contiene a los n puntos para situar
en su centro la central. Afortunadamente, como estudió Matemáticas,
sabe que lo que busca (un círculo) está determinado por tres
de los puntos que tiene (o tal vez dos si son diametralmente opuestos en
el círculo). Así que está salvado. Tomará los
puntos de tres en tres de todas las formas posibles y comprobará
en cada caso si los demás puntos están dentro del círculo
que determinan (debe hacer lo mismo con cada pareja de puntos y el círculo
para el que son diametralmente opuestos). El menor de los círculos
que satisfagan la condición es el buscado y su centro el lugar más
adecuado. Cuando se pone a ejecutar su algoritmo cae en la cuenta de que
va a tardar mucho. Además, a partir de ahora, va a tener que realizar
muchas veces esta tarea, pues le han nombrado coordinador europeo de planificación
de centros de control de emergencias y rescate. Decide entonces dedicar
un tiempo a pensar si existe otra forma de resolver el problema que requiera
menos tiempo.
En la escena está el subdirector general de la consejería
de medio ambiente, recientemente renombrada consejería de política
ambiental para que quede claro que no sólo se ocupa de medio ambiente
sino del ambiente entero. En la mesa tiene también el plano de la
región con los pueblos representados por puntos. Su problema es
bien diferente. Debe decidir dónde situar el vertedero de la comarca
(con incineradora incluida). Sabe que nadie quiere tenerlo cerca. Su única
alternativa es buscar un lugar lo más alejado posible de cualquier
pueblo. Afortunadamente, recuerda las muchas Matemáticas que estudió
en su carrera de Ingeniería Industrial antes de hacer el Master
en Organización Empresarial y conserva los útiles de dibujo
con aprecio, aunque ahora maneja programas de dibujo con ordenador. Al
pensar en el problema se da cuenta enseguida de que lo que tiene que hacer
es buscar el mayor círculo vacío de puntos para situar el
vertedero en el centro de ese círculo. Sabe que el círculo
estará determinado por tres de los puntos. También él
se da cuenta de que mirar todos los círculos determinados por cada
tres puntos es un procedimiento que le llevará demasiado tiempo.
Es entonces cuando se acuerda de que el sábado ha quedado a cenar
con su amigo Félix, aquél compañero del instituto
que empezó Industriales con él y al fin lo dejó porque
lo que realmente le gustaban eran las Matemáticas.
De nuevo los controladores aéreos. A punto de iniciar
una huelga por un problema sindical. El sindicato reclama un complemento
salarial en función del número de aviones que cada controlador
supervisa. Al analizar a fondo la reivindicación se llega a la conclusión
de que, más que el número de aviones, el estrés lo
causa su densidad. Así se llega a definir el factor de estrés.
El factor de estrés viene dado por el cociente entre el número
de aviones y la superficie que abarcan. Tras una acalorada discusión
geométrica en las negociaciones con la administración, se
llega al acuerdo de que "la superficie que abarcan" es el área del
polígono de menor perímetro que contiene a todos los puntos.
El factor de estrés hay que calcularlo 24 veces al día para
hacer la media mensual de cada controlador. El cálculo del factor
de estrés pasa a ser otro motivo de estrés para los controladores.
Por suerte, Félix, uno de ellos, es matemático y consigue
resolver el problema de un modo eficiente: Decide triangular la nube de
puntos y sumar las áreas de sus triángulos. Además
descubre que, si triangula adecuadamente, resuelve de paso el problema
del par más próximo al que andaba dando vueltas y también
el problema que le planteó el sábado, mientras cenaban, su
amigo el subdirector general de medio ambiente.
Una triangulación de una nube de puntos del plano es una familia maximal de triángulos de interiores disjuntos cuyos vértices son puntos de la nube y en cuyo interior no hay ningún punto de la nube.
Puede obtenerse una triangulación añadiendo, mientras sea posible, segmentos rectilíneos que unan puntos de la nube que no atraviesen a los segmentos ya considerados.
Dos triangulaciones de una misma nube de puntos
Sobre las triangulaciones de una misma nube de puntos cabe hacerse varias preguntas. Entre ellas las siguientes:
Superficie poliédrica de tipo terreno
Entre otros muchos usos, las triangulaciones se emplean para interpolar una función en una nube de puntos del espacio. El problema es el siguiente:
Dados n puntos en el espacio, tales que no hay dos en la misma vertical, hallar una superficie poliédrica cuyos vértices sean los puntos dados y que no contenga dos puntos en la misma vertical.
Este tipo de superficies poliédricas se llaman de tipo terreno. De hecho se emplea este problema en cartografía para obtener un modelo aproximado del terreno a partir de las coordenadas espaciales de unos cuantos miles de puntos.
Cualquier triangulación de los puntos del plano XY, que se obtienen proyectando ortogonalmente los puntos de la nube, da lugar a una superficie en las condiciones pedidas con tan sólo "levantarla", llevando los vértices de la triangulación a los puntos originales en el espacio.
Normalmente, al menos en cartografía o ingeniería, interesa que, puntos cuyas proyecciones son puntos próximos, estén conectados por aristas de la superficie poliédrica. Esto da interés al siguiente problema cuya solución es lo que se conoce como la triangulación de Delone:
Dada una nube de puntos del plano, hallar una triangulación en la que puntos próximos estén conectados entre sí por una arista. O, dicho de otro modo, en la que los triángulos sean lo más regulares posible.
Formalicemos el problema: Sea P un conjunto de n puntos del plano. Para cada triangulación T del conjunto P el vector de ángulos es el vector formado por los ángulos de todos los triángulos de T ordenados de menor a mayor. No es difícil demostrar que cualquier triangulación de un mismo conjunto de puntos tiene exáctamente el mismo número de triángulos, y, por tanto, los vectores de ángulos son todos de la misma dimensión. (La demostración se basa en la fórmula de Euler que relaciona el número V de vértices con el de caras C y el de aristas A en un poliedro: C+V-A=2 ). Se verifica que el orden lexicográfico definido en el conjunto de los vectores de ángulos de un conjunto de puntos P es un orden parcial que posee un elemento máximo, es decir, mayor que cualquier otro. La triangulación correspondiente a dicho vector es la triangulación de Delone.
El siguiente resultado sencillo permitirá obtener de una forma muy simple la triangulación de Delone partiendo de una triangulación cualquiera:
Intercambio de aristas (flip)
Cuatro puntos en posición convexa (como los de la figura) tienen dos posibles triangulaciones (las dos de la figura). Aquella en la cual los círculos circunscritos son vacíos, es decir, no contienen en su interior al cuarto punto, es la que tiene un vector de ángulos mayor. La demostración es un ejercicio para el lector (Sólo requiere conocimientos básicos de trigonometría).
A la operación que consiste en sustituir una diagonal por la otra en un cuadrilátero le llamaremos intercambio de aristas. Diremos que es un flip cuando mejora el vector de ángulos (como en el caso de la figura).
Obsérvese que si en una triangulación de un conjunto de puntos efectuamos un flip en el cuadrilátero determinado por la unión de dos triángulos adyacentes (que formen un cuadrilátero convexo), el vector de ángulos será estrictamente mayor.
Llamaremos ilegal a toda arista de una triangulación que pertenece a dos triángulos tales que forman un cuadrilátero convexo y tal que si se intercambia dicha arista por la otra diagonal del cuadrilátero mejora el vector de ángulos. Las aristas ilegales son aquellas para las que es posible hacer un flip.
La observación anterior es la clave del siguiente algoritmo:
Algoritmo (Triangulación de Delone):
Entrada: Un conjunto finito de puntos del plano
Paso 1: Obtener una triangulación cualquiera
del conjunto.
Paso 2: Mientras haya aristas ilegales en la
triangulación
El polígono de menor perímetro
que contiene a una nube de puntos del plano se llama envolvente convexa
del conjunto. La envolvente convexa forma parte de todas las triangulaciones
de un conjunto. A los vértices de la envolvente convexa se les llama
puntos extremos o frontera del conjunto. A los puntos restantes
se les llama interiores.
Vamos a emplear el siguiente problema como modelo para entender cuál es el objetivo principal de la Geometría algorítmica.
Problema: Dada una nube de puntos del plano P, hallar la envolvente convexa C( P ).
Veamos primero cuatro maneras diferentes de resolver el problema para después analizar cuál de ellas es la mejor.
Solución 1: (búsqueda de los extremos mediante la eliminación de puntos interiores) Teniendo en cuenta que un punto es interior si y solo si pertenece a un triángulo determinado por otros tres, podemos eliminar los puntos interiores seleccionando los puntos del conjunto de tres en tres de todas las formas posibles y eliminando los puntos que estén incluidos en alguno de dichos triángulos. De esta forma nos habremos quedado con los puntos extremos. Para obtener la envolvente convexa, falta encontrar sus aristas. De momento dejaremos sin precisar cómo hacerlo.
Solución 2: (búsqueda de las aristas) Las aristas de la envolvente convexa se caracterizan por la siguiente propiedad: la recta que determinan deja el resto de los puntos en un mismo semiplano de los que esa recta define. Empleando esta propiedad, un algoritmo para hallar la envolvente convexa consiste en escoger los puntos de dos en dos de todas las formas posibles y, para cada elección, comprobar si el resto de los puntos están en un mismo semiplano. Haciendo esto, encontramos las aristas de la envolvente convexa. Conviene, además, ordenarlas para describir la envolvente convexa mediante la lista circular de sus vértices según se encuentran al recorrerla en sentido horario. Dejamos tambien sin detallar cómo hacer este último paso.
Solución 3: (método de Jarvis) El punto de menor ordenada es extremo (si hubiera varios, el que tenga mayor abscisa). Si buscamos, de los demás puntos, aquel que unido a éste defina la recta de menor pendiente, habremos encontrado otro extremo y además el segmento que los une será una arista de la envolvente convexa. Para hallar el resto podemos repetir el proceso a partir del segundo punto considerado.
Solución 4: (método de Graham) Calculamos
la envolvente convexa superior del siguiente modo. Ordenamos de izquierda
a derecha , es decir en orden creciente de abscisas, los puntos de la nube.
Así se obtiene una poligonal. Cada vértice de esa poligonal
que quede por debajo del segmento que une el vértice anterior y
el vértice posterior a él, se elimina uniendo éstos
para formar una poligonal con un vértice menos. Cuando esta operación
no pueda realizarse más habremos obtenido la envolvente convexa
superior. La envolvente inferior se calcula de forma análoga, eliminando
esta vez los puntos que estén por encima del segmento que une el
anterior y el posterior.
Analicemos ahora los algoritmos propuestos. En el primer caso, el
número de operaciones superará, al menos, al número
de triángulos que podemos elegir con los n puntos multiplicado
por el número de puntos restantes, n-3, pues, para cada uno
de ellos, debemos verificar si es interior o no al triángulo. Téngase
en cuenta que en el peor caso no eliminaremos ni uno solo de los puntos
(en este caso se dice que los puntos están en posición convexa).
Por tanto, al menos, habrá que realizar 
operaciones.
Esto es una función de n de orden O(
).
En el segundo caso las cosas mejoran, pero no demasiado. Para cada par
de puntos, y hay 
pares,
hay que hacer (n-2) comprobaciones adicionales. El resultado es
que, al menos, tendremos que realizar un número de operaciones de
orden O(
). En el método
de Jarvis cada nuevo vértice y, por tanto, cada nueva arista de
la envolvente se obtiene hallando el mínimo en la lista de las pendientes
correspondientes. Esto se puede hacer con un número de operaciones
proporcional al número de puntos. En el peor caso habrá que
repetir n veces la búsqueda de aristas, por lo que se puede
llevar a cabo con un número de operaciones que, a lo más,
será de orden O(
). El
último método propuesto consta de dos fases: La ordenación
y la eliminación de puntos interiores. La eliminación se
puede realizar con un número de operaciones proporcional al número
de puntos que intervienen. Para la ordenación existen algoritmos
que la llevan a cabo con un número de operaciones de orden O(n.logn).
En consecuencia, es posible ejecutar el algoritmo en cualquier caso sin
superar O(n.logn) operaciones.
Ahora conviene pararse a observar lo que significan las diferencias
que hemos encontrado. La siguiente tabla muestra los valores de las funciones
que hemos mencionado para distintos valores de n.
|
|
|
|
|
|
|
|
10.000
|
100.000.000
|
1.000.000.000.000
|
10.000.000.000.000.000
|
|
|
1.000
|
1.000.000
|
1.000.000.000
|
1.000.000.000.000
|
|
|
100
|
10.000
|
1.000.000
|
100.000.000
|
|
|
23
|
460
|
6907
|
92103
|
Tabla de valores de las funciones ,,,
nlogn, para algunos valores de n
De ella se puede deducir que un procesador con una velocidad
de proceso de un MIP (millón de instrucciones por segundo) tardaría
al menos 11 dias en obtener la envolvente convexa de 1000 puntos con el
primero de los algoritmos. Con los demás algoritmos tardaría
la misma máquina 16 minutos, 1 segundo y 6 milésimas de segundo
respectivamente. Las diferencias se hacen más patentes comparando
los 316 años que tardaría en ejecutarse el primer algoritmo
para 10.000 puntos frente a una centésima de segundo que tardaría
el último.
En su libro sobre los principios de la filosofía, René Descartes sostiene que el sistema solar está formado por vórtices y acompaña su escrito con el grabado de la figura.
Más tarde, Gustav Lejeune Dirichlet, Georgy Voronoi, A.H.Thiessen y otros autores de muy diferentes áreas han vuelto a redescubrir la idea que subyace en el grabado de Descartes: Un conjunto de puntos del espacio descompone a éste en regiones cada una de las cuales es la formada por los puntos más próximos a cada uno de ellos.
Volvamos a las triangulaciones de Delone pero miremos las cosas
al revés. Cambiemos en la triangulación de Delone las caras
por vértices y los vértices por caras del siguiente modo.
Para cada triángulo consideremos el centro de la circunferencia
circunscrita y unamos dos de estos centros siempre que sus triángulos
correspondientes compartan una arista. Las aristas exteriores, que solo
pertenecen a un triángulo las sustituiremos por semirectas con origen
en el centro correspondiente al triángulo y dirección perpendicular
a la arista.
Triangulación de Delone y el diagrama dual
De esta manera obtenemos otra división del plano conocida, según en qué contexto, por diagrama de Voronoi, subdivisión de Dirichlet, o subdivisión en regiones de Thiessen.
Cada una de las nuevas regiones resulta ser el lugar geométrico de los puntos del plano más próximos a cada uno de los puntos del conjunto inicial.
Diagrama de Voronoi
Esta estructura, dual de la triangulación de Delone, contiene también la información sobre proximidad del conjunto de puntos inicial. Veamos algunas situaciones reales en las que los diagramas de Voronoi son útiles.
Telefonía móvil. Los teléfonos móviles transmiten y reciben señales de las antenas situadas en puntos fijos y que no deben estar muy distantes del aparato. Para analizar el emplazamiento de las antenas hay que tener en cuenta el área que corresponde a cada una de las antenas de una zona. Por otra parte, la región de Voronoi de cada una determina la zona desde la cual los teléfonos deberían conectar a través suyo.
Control aéreo. La región de Voronoi de cada centro de control aéreo indica la zona más próxima a dicho centro y, en consecuencia, determina la región que debería ser controlada desde ese centro de control.
Transporte de materias peligrosas. Si se quiere establecer una línea de transporte de materias nocivas o peligrosas (gaseoductos, oleoductos, líneas de alta tensión, etc. ) lo adecuado es alejarse lo más posible de los centros de población. Esto lleva a buscar caminos equidistantes de dos o más centros, lo que equivale a trazar la línea por las aristas del diagrama de Voronoi.
Análisis de poblaciones de especies vegetales. De un monte se ha obtenido, mediante fotografía aérea, la disposición de los árboles así como su especie. Un modo de analizar la zona de influencia de cada especie consiste en hallar el diagrama de Voronoi de los puntos que representan a los árboles y eliminar las aristas que separan regiones correspondientes a árboles de la misma especie. Así se obtienen las regiones (conexas o no) correspondientes a cada especie.
Análisis de la distribución de servicios (correos, farmacias, hospitales, etc.) ¿Dónde situar el nuevo centro comercial de la cadena Pryma? El asesor comercial sabe que debe buscar el lugar en el plano de forma que su región de Voronoi sea lo mayor posible en el diagrama obtenido a partir de puntos que representan los centros comerciales ya existentes (incluidos los de la competencia) junto con el nuevo centro. ¿A qué oficina de correos debo ir? A aquella cuya región de Voronoi contenga el punto donde me encuentro. El diagrama, en este caso, se ha de calcular con los puntos que corresponden a las oficinas de correos.
Naturalmente la realidad es en general más compleja que
los modelos mencionados. Esto no debe desilusionar al geómetra sino
todo lo contrario (¡nuevos problemas en que pensar!). Salvo los desplazamientos
en helicóptero, las distancias entre puntos normalmente no son euclídeas.
Esta ha sido una buena razón para generalizar los diagramas de Voronoi
y su estudio en numerosos espacios métricos diferentes. Piénsese
cómo será la región de Voronoi de un punto del mapa
cuando se encuentra a un lado de una autopista que no puede atravesarse
salvo por los pasos elevados que hay cada 30 kilómetros.
Si consideramos el problema de la envolvente convexa en el
espacio, el problema consiste en hallar el poliedro de menor superficie
que contiene a una nube de puntos. La solución es un poliedro convexo
cuyos vértices son algunos puntos de la nube. No entraremos en los
detalles de cómo calcular envolventes convexas en el espacio. No
todas las técnicas del plano admiten una generalización en
el espacio. Piénsese por ejemplo que el algoritmo de Jarvis carece
de sentido en el espacio pues se basa en la ordenación angular de
los puntos, cosa que en el espacio no tiene sentido. Algo similar le ocurre
al de Graham. A pesar de ello, hay algoritmos cuya complejidad sigue siendo
O( nlogn ) en el espacio.
Supongamos que disponemos de un algoritmo para calcular envolventes convexas en el espacio, y, puestos a suponer, que sea el bueno, es decir, el que lo hace con O( nlogn ) operaciones. Consideremos una nube de puntos en el plano. Para cada punto de coordenadas (x,y) consideremos el punto (x,y, x2+y2) en el espacio. Ahora calculemos con nuestro magnífico algoritmo la envolvente convexa de la nube que hemos obtenido así en el espacio. El resultado es un poliedro convexo con tantos vértices como puntos teníamos al principio y cada uno de los cuales está justo encima del correspondiente del plano. Dejemos caer sobre el plano XY las aristas de la parte inferior del poliedro (es decir, las que al hacerlo no atraviesan el interior del poliedro). El resultado es... ¡la triangulación de Delone!
Teniendo en cuenta cómo hemos definido el diagrama de Voronoi en la sección anterior y el resultado (¿sorprendente?) anterior, podemos concluir afirmando el título de esta sección: El diagrama de Voronoi de n puntos del plano, su triangulación de Delone y la envolvente convexa de los puntos que se obtienen elevando los n puntos al paraboloide, son esencialmente la misma cosa.
La Matemática consiste esencialmente en esto: Encontrar
aspectos comunes en situaciones diferentes. En definitiva, matar dos pájaros
(o más) de un tiro (tómese esto como una expresión
y no en sentido literal, especialmente en época de veda).
Hablemos por fin de los cuatro problemas planteados en la introducción.
El cuarto es claro que podemos resolverlo empleando uno de los algoritmos
de cálculo de la envolvente convexa. Emplearemos naturalmente uno
de los "rápidos". Como sabemos, el número de operaciones
que requiere uno de estos algoritmos en el peor caso es O( nlogn
). Un análisis probabilístico prueba sin embargo que hay
algoritmos que resuelven el problema con un número de operaciones
lineal respecto del número de puntos ( los llamados algoritmos aleatorizados
).
El problema 3 puede resolverse empleando como paso previo la triangulación de Delone. Si disponemos de esta triangulación de la nube de puntos, el círculo mayor vacío es uno de los círculos circunscritos a uno de los triángulos de Delone. Como la relación entre vértices y triángulos en toda triangulación es lineal (según la conocida fórmula de Euler ), resulta que el número de operaciones suficientes para resolver el problema es del mismo orden que el del cálculo de la triangulación de Delone, es decir, O( nlogn ).
El problema 1 también queda resuelto fácilmente conociendo la triangulación de Delone de la nube. En efecto, necesariamente una de las aristas de la triangulación conecta al par de puntos más próximos. Así, una vez calculada la triangulación, lo único que debemos hacer es revisar cuál de sus aristas es la más corta. Como el número de vértices también es proporcional al de áristas (según la fórmula de Euler), la complejidad de este método es de nuevo en el peor caso igual a la del cálculo de la triangulación de Delone.
Queda por resolver el problema del menor círculo que contiene
a n puntos. A pesar de su apariencia similar con el problema 3,
es bien diferente. El estudio de este problema se remonta a 1857 cuando
lo formuló James J. Sylvester en su trabajo "A question on the
geometry of situation". Desde entonces ha sido un problema muy estudiado.
En 1983 Megiddo publicó un algoritmo óptimo de complejidad
O(n) en su artículo "Linear time algorithms for linear programming
in 
and related problems".
En esta sección se recoge la información
básica sobre bibliografía y enlaces en Internet relacionados
con la Geometría algorítmica. No pretende ser exhaustiva
sino sólo servir de punto de partida. En cada apartado se dan primero
algunas referencias sobre diagramas de Voronoi y triangulaciones de Delone
por ser este el tema central sobre el que se ha basado el presente artículo.
Están dedicadas a aquellos que estén interesados directamente
en el tema. A continuación se dan referencias generales sobre Geometría
algorítmica.
Sobre triangulaciones de Delone y diagramas de Voronoi.
Sobre diagramas de Voronoi:
Otra interesante es http://www.voronoi.com
.