Descubriendo la Geometría algorítmica


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.

 

 1. Introducción

 Uno.


 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…
 

 Dos.


 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.
 

 Tres.


 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.
 

 Cuatro.


 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.
 

         2. Boris Nikolaevich Delone


1890 -1980 Nació en San Petersburgo (Rusia), aunque con ascendiente francés. Trabajó principalmente en Álgebra y Geometría de los números. Hizo un trabajo importante en análisis estructural de los cristales. Además de un matemático importante fue un famoso escalador. (Más informaciónen http://www-history.mcs.st-andrews.ac.uk/history/Mathematicians/Delone.html )
 

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:

  1. ¿Cuántas triangulaciones diferentes de la misma nube existen?
  2. ¿Cuál de ellas es la mejor en algún aspecto determinado?
Uno puede pensar que, como el número de puntos de la nube es finito, el número de posibles triángulos con vértices en ellos es finito y, en consecuencia, el número de triangulaciones es finito. Correcto. Así, un modo de averiguar cuál de ellas es la mejor según una condición dada consiste en calcular dicha condición para todas ellas y comparar. Correcto. Un inconveniente de éste método en la práctica es precisamente la respuesta a la primera pregunta. En general, para una nube de n puntos existe una cantidad de triangulaciones que depende exponencialmente de n. Esto significa que, cuando n sea medianamente grande, el número de triangulaciones es lo suficientemente elevado como para que ningún computador, por sofisticado que sea, pueda calcularlas todas.
     

    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

          hacer el flip correspondiente.
     Salida: La triangulación de Delone del conjunto
     Fin.
     
     

      El paso 1 del algoritmo es de nuevo un ejercicio para el lector. Una sugerencia es la siguiente: Supóngase que la mitad de los puntos que están a la derecha están triangulados, así como la mitad de los puntos que están a la izquierda. Lo que resta es triangular la franja central. Si sabemos hacer esto, la nube completa la podremos triangular de forma recursiva descomponiendo sucesiva-mente cada mitad en otras dos mitades.
     

        3. Envolvente convexa


 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.
 
 

Un conjunto de puntos y su envolvente convexa

  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.
 

 Análisis.


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.
 

 n
10
100
1.000
10.000
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
nlogn
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.
 
 
 

        4. Descartes, Dirichlet, Voronoi, Thiessen,… ( la dualidad )


  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.
 
 
 

        5. Triangulación de Delone, envolvente convexa, diagrama de Voronoi: tres caras de la misma estructura


  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).
 
 

        6. Las soluciones


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".
 
 
 

        7. Bibliografía y enlaces de interés


 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.
 

Libros


Sobre triangulaciones de Delone y diagramas de Voronoi.

Sobre Geometría algorítmica en general. Textos de introducción: Textos enciclopédicos:

Artículos


 Sobre diagramas de Voronoi:

Franz Aurenhammer and Rolf Klein,"Voronoi Diagrams", Department of Computer Science, FernUniversität, Hagen 1996. Es un artículo amplio y muy general que forma parte como capítulo del libro de Sack y Urrutia mencionado arriba. Puede obtenerse la versión preliminar en la dirección de Internet http://wwwpi6.fernuni-hagen.de/Publikationen/tr198.pdf General: Existe una base de datos pública y gratuita que contiene la práctica totalidad de las referencias sobre Geometría Algorítmica en el mundo. Un espejo de esta base puede consultarse en la Universidad Politécnica de Cataluña en la dirección

http://www-ma2.upc.es/~geomc/geombib/geombibe.html

Enlaces en Internet

  1. Sobre diagramas de Voronoi:

  2. Existen numerosas direcciones en Internet sobre diagramas de Voronoi. Una de las mejores es la aplicación Java "VoroGlide" del grupo de Praktische Informatik VI, FernUniversität Hagen. Su dirección es  http://wwwpi6.fernuni-hagen.de/Geometrie-Labor/VoroGlide/  .

    Otra interesante es http://www.voronoi.com .
     

  3. Generales

  4. También hay numerosas direcciones en Internet sobre Geometría Algorítmica. El "portal" por excelencia es la página de Jeff Erickson (http://compgeom.cs.uiuc.edu/~jeffe/compgeom/) en donde hay enlaces a todo aquello que tiene que ver con la Geometría algorítmica en el mundo. La página de Godfried Toussaint (http://cgm.cs.mcgill.ca/~godfried/computational.geometry.html) es así mismo particularmente recomendable.
     
  5. Software
Nina Amenta mantiene una página que recopila enlaces a direcciones con programas de Geometría algorítmica. Gran parte es software libre que puede obtenerse por la red. (http://compgeom.cs.uiuc.edu/~jeffe/compgeom/software.html#nina)