Envolvente convexa, triangulacin

de Delaunay y diagrama de Voronoi:

tres estructuras geomtricas en una,
con muchas aplicaciones
por
Manuel Abellanas Oar, Universidad Politcnica de Madrid
Este artculo muestra la relacin entre tres de las estructuras ms estudiadas
en Geometra Computacional: la envolvente convexa, la triangulacin de Delau-
nay y el diagrama de Voronoi de un conjunto nito de puntos del plano. El gran
inters y la extensa bibliografa que existe sobre estas tres estructuras se debe fun-
damentalmente a sus mltiples aplicaciones. Mostramos aqu dos de ellas a modo
de ejemplo.
1. Envolventes convexas
Un conjunto de puntos del plano es convexo si el segmento que une dos cua-
lesquiera de sus puntos est totalmente contenido en el conjunto. As, el propio
plano es un conjunto convexo. Tambin lo son los semiplanos determinados por
una recta, tanto si incluyen el borde como si no (semiplanos cerrados o abiertos).
La interseccin de conjuntos convexos es un conjunto convexo, ya que si dos pun-
tos estn en la interseccin, estn en cada uno de los conjuntos convexos que la
forman, por lo que el segmento que los une est totalmente contenido en todos
ellos y, por tanto, en la interseccin. De lo anterior se deduce que las regiones
obtenidas por interseccin de semiplanos son conjuntos convexos. Si la intersec-
cin de una cantidad nita de semiplanos cerrados es acotada y no vaca, es un
polgono convexo.
157
158 Un Paseo por la Geometra
Se llama cierre convexo de un conjunto de puntos del plano al menor conjunto
convexo que lo contiene (entendiendo menor segn el orden que proporciona la
inclusin de conjuntos).
Es claro que el cierre convexo de cualquier conjunto es un conjunto convexo.
Tambin es fcil ver que el cierre convexo de un conjunto coincide con l mismo
si, y solo si se trata de un conjunto convexo. Convexicar un conjunto es hallar
su cierre convexo. La convexicacin de conjuntos tiene numerosas aplicaciones.
Aqu nos planteamos el caso ms sencillo de la convexicacin de conjuntos ni-
tos de puntos. Llamaremos envolvente convexa a la frontera del cierre convexo.
La envolvente convexa determina el cierre convexo.
Veamos cmo resuelve el problema un equipo pluridisciplinar:
Buscando un algoritmo para hallar el cierre convexo de un conjunto nito de
puntos del plano, tres personas mantenan la siguiente conversacin:
- (A) El cierre convexo es el menor conjunto convexo que contiene al conjun-
to dado.
- (B) Como la interseccin de convexos es convexo, el cierre convexo de un
conjunto es la interseccin de todos los conjuntos convexos que lo con-
tienen.
- (C, que es informtico) Son ustedes matemticos, verdad?
- (A y B sorprendidos) S, porqu lo dice?
- (C) Porque han hecho armaciones interesantes y ciertas, pero intiles!
En efecto, ninguna de las alternativas propuestas sirve para hallar el cierre
convexo de un conjunto, aunque sea nito, pues ambas requieren la intervencin
de una cantidad innita de objetos. Ninguno de los dos mtodos acabara nunca.
Un ingeniero fsico que pasaba por all y oy la conversacin, intervino en-
seguida diciendo:
- Vaya cosa ms simple! Lo nico que tienen que hacer es representar los
puntos sobre una tabla, clavar, pero no del todo, un clavo en cada punto
sobre la tabla y soltar una goma elstica que rodee a todos los clavos. De
inmediato la goma elstica les dir qu forma tiene el cierre convexo.
Esta propuesta no gust tampoco al informtico, porque l estaba empeado
en desarrollar un programa que permitiera resolver el problema empleando su or-
denador. Sin embargo, le sirvi para observar empricamente algunas propiedades
del cierre convexo de un conjunto nito de puntos mientras dej a los matemticos
discutiendo con el ingeniero fsico sobre las propiedades de la contraccin de las
gomas elsticas.
Estas son las observaciones que hizo el informtico:
Envolvente convexa, triangulacin de Delaunay, diagrama de Voronoi 159
Observacin 1: El cierre convexo de n puntos es un polgono convexo
cuyos vrtices son puntos del conjunto dado.
Observacin 2: Una buena manera de representar un polgono convexo
puede ser la enumeracin de sus vrtices en el mismo orden en que aparecen
al recorrer la frontera del polgono.
Observacin 3: De las observaciones anteriores se deduce que el proble-
ma de calcular el cierre convexo de n puntos del plano es un problema de
seleccin ordenada. Es decir, se trata de seleccionar un subconjunto de los
puntos dados y ordenarlos de la forma adecuada.
Estas observaciones llamaron la atencin de los matemticos, que inmediata-
mente dieron por resuelto el problema:
- Ya tienes algoritmo - dijeron al unsono.
- Como tu conjunto de puntos es nito, toma cada uno de sus subconjuntos
y ordnalo de todas las formas posibles. Analiza cada una de esas orde-
naciones. Cuando encuentres aquella que describe un polgono convexo tal
que todos tus puntos estn contenidos en l, esa ser la solucin. Ten en
cuenta que comprobar si una lista de puntos son los vrtices de un polgono
convexo es sencillo, ya que slo tienes que comprobar que el siguiente pun-
to a dos consecutivos est siempre a la izquierda (o siempre a la derecha)
de la recta que determinan. Para eso puedes emplear reas signadas
1
.
El informtico, animado por los consejos de los matemticos implement el
algoritmo sin demasiado esfuerzo. Tuvo, eso si, que encontrar un algoritmo que
averige si un punto est contenido en un polgono convexo, pues es una de las
comprobaciones que requera el algoritmo dado por los matemticos.
Al terminar, prob con algunos ejemplos sencillos y todo fue bien. Lo malo
vino cuando trat de emplear su programa con los casos reales a los que deba
enfrentarse. Estos eran conjuntos de miles de puntos tomados con un escner de
piezas fabricadas por el cliente que le haba solicitado el programa. Con el primero
de los casos el ordenador pareci entrar en un sueo profundo del que no despert
hasta que, tras varios das, cansado de esperar, el informtico interrumpi el pro-
ceso y decidi buscar otra alternativa.
1
El rea signada determinada por tres puntos del plano A(a
1
, a
2
), B(b
1
, b
2
) y C(c
1
, c
2
) es el
rea del tringulo que los tiene como vrtices con el signo correspondiente a la orientacin del
tringulo. Se puede calcular con la expresin
1
2

1 1 1
a
1
b
1
c
1
a
2
b
2
c
2

.
160 Un Paseo por la Geometra
Un conjunto de n elementos tiene muchos subconjuntos: 2n. Adems, el n-
mero de ordenaciones de cada uno de ellos, tambin es muy elevado. Si tiene k
elementos, hay k! ordenaciones. Echando cuentas por lo bajo, resulta que para mil
puntos tendramos que analizar 2
1000
conjuntos. Aunque nuestro ordenador fuera
capaz de analizar cada uno de ellos en una millonsima de segundo, cosa del
todo imposible hoy da, teniendo en cuenta que el anlisis incluye evaluar todas
las permutaciones de sus elementos, necesitaramos muchos miles de aos para
completar el clculo!
Esta historia, real como la vida misma, da idea de cul es la misin de la
Geometra Computacional (y de la algortmica en general). Se trata de resolver
problemas geomtricos de forma algortmica, pero eciente. En el caso que nos
ocupa, hay muy buenos algoritmos. Veamos dos de ellos con nombre propio: el
algoritmo de Graham [6] y el de Jarvis [7]. Los dos emplean como pieza bsica el
rea signada que se ha mencionado antes.
Algoritmo de Graham
El algoritmo consta de dos fases.
En la primera se ordenan los puntos angularmente alrededor de un punto inte-
rior al cierre convexo. Para hallar un punto interior al cierre convexo basta tomar
el baricentro de tres de los puntos dados que no estn alineados. La ordenacin es
una tarea habitual en algortmica que se repite un gran nmero de veces. Por eso
hay desarrollados buenos algoritmos para hacerlo. En este caso, a pesar de que se
trata de una ordenacin angular, no es preciso recurrir a funciones trigonomtricas
(que complicaran el clculo efectivo). Para ordenar la lista basta emplear como
funcin bsica el rea signada.
En la segunda se suprimen de la lista ordenada los puntos que no son vrtices
del cierre convexo. Para ello se hace un recorrido de la lista (conocido como el
scan de Graham) en el que, de nuevo, se emplean reas signadas para decidir
si un punto debe ser eliminado o no. Si los puntos estn ordenados en sentido
antihorario, el rea signada de los puntos P
i1
, P
i
, P
i+1
nos dice si el punto P
i
debe ser eliminado. En efecto, si el rea no es positiva, el punto P
i
es interior al
tringulo P
i1
, O, P
i+1
, donde O es el centro de la ordenacin, y, por tanto, interior
al cierre convexo. En este caso debe ser eliminado. Para que esta segunda fase
proporcione la lista correcta de vrtices del cierre convexo es preciso incluir un
detalle ms: cada vez que se elimine un punto de la lista, se debe dar un paso atrs
en el recorrido, ya que al eliminar un punto puede suceder que los tres que pasan a
ser consecutivos den lugar a un rea signada no positiva, en cuyo caso habra que
eliminar el punto intermedio de nuevo.
Este algoritmo realiza solo tres operaciones bsicas: comparaciones de n-
meros, sumas y productos. Adems, el nmero total de estas operaciones que se
Envolvente convexa, triangulacin de Delaunay, diagrama de Voronoi 161
realizan es del orden
2
O(n log n). Para hacerse una idea de lo que esto signica, un
ordenador personal normal de hoy da puede calcular el cierre convexo de varios
millones de puntos en menos de un segundo. Queda claro, por tanto, el gran inters
que tiene encontrar algoritmos ecientes, pues podemos pasar de estar ante una
solucin correcta pero intil a una solucin til.
Algoritmo de Jarvis
El algoritmo de Jarvis empieza buscando un vrtice del cierre convexo y, a par-
tir de l, busca sucesivamente el resto de los vrtices en el orden en que aparecen
en la frontera. El primer vrtice V
1
puede ser el punto de menor ordenada (si hu-
biera varios, el de menor abscisa de entre ellos). El siguiente, V
2
, es aqul tal que
la recta orientada que pasa por V
1
y V
2
deja el resto de los puntos a su izquierda.
Lo mismo se repite sucesivamente, de forma que la recta orientada determinada
por V
i
y V
i+1
deje todos los dems puntos a su izquierda hasta obtener de nuevo
V
1
.
En cada paso se encuentra un nuevo vrtice V
i+1
del cierre convexo. Para ello
se emplea de nuevo la funcin rea signada: el signo del rea signada de V
i
, P
i
,
P
j
, indica cul de los dos puntos P
i
o P
j
precede al otro en el orden angular
respecto de V
i
, y, por tanto, cul de los dos es candidato a ser el siguiente vrtice
del cierre convexo. Si se compara sucesivamente el candidato obtenido con los
puntos restantes, al nal se obtiene el vrtice buscado.
Para hallar un nuevo vrtice el algoritmo recorre la lista de puntos dados, de
manera que en total el algoritmo realiza una cantidad de operaciones del orden
O(nh) siendo h el nmero de vrtices del cierre convexo. En el pero caso, cuando
el nmero de vrtices sea proporcional al de puntos dados, la complejidad del al-
goritmo es O(n
2
) y, por tanto, peor que el de Graham. Sin embargo, este algoritmo
aventaja al de Graham en aquellos casos en los que el cierre convexo tiene pocos
vrtices. En particular, si el nmero de vrtices se puede considerar constante
respecto al nmero de puntos dados, el algoritmo de Jarvis llega a ser de comple-
jidad lineal superando notablemente al de Graham. Este es un buen ejemplo de
algoritmo de complejidad dependiente del resultado.
2. Triangulacin de Delaunay
Para entender qu es una triangulacin de un conjunto de puntos del plano sugiero
al lector realizar el siguiente experimento:
1. Dibujar n puntos en una hoja de papel (n debera ser al menos 10 para que
no resulte demasiado sencillo y no muy grande para que no resulte demasiado
2
Es frecuente medir la complejidad de los algoritmos mediante el orden de magnitud de las
funciones que indican el nmero de operaciones consideradas bsicas necesarias para ejecutar el
algoritmo en el peor caso posible. Para ello se emplea la notacin de Landau O( f (n)).
162 Un Paseo por la Geometra
largo el experimento)
3
.
2. Mientras sea posible, conectar dos de los puntos dibujando un segmento
(rectilneo) que no corte a otro segmento previamente dibujado.
El resultado del experimento es (debera ser) una triangulacin del conjunto
de puntos dado
4
.
Si el lector ha realizado el experimento, se habr dado cuenta de que ha tenido
muchas alternativas para dibujar segmentos, de las cuales ha ido seleccionando
uno segn su propio criterio o gusto. Es cierto que las alternativas se van reducien-
do segn vamos dibujando segmentos. De hecho, al nal, slo queda un posible
segmento para ser dibujado, tras lo cual no es posible dibujar un nuevo segmento
sin producir cortes. En todo caso el nmero de diferentes triangulaciones que se
pueden obtener partiendo del mismo conjunto de puntos es elevado. Contar cun-
tas triangulaciones hay es un problema interesante de la Geometra combinatoria.
Las triangulaciones juegan un papel importante en numerosas aplicaciones,
en especial en modelizacin matemtica. Los mtodos de los elementos nitos se
basan, en el caso bidimensional, en triangulaciones de conjuntos de puntos del
plano y dependen en gran medida de la triangulacin elegida. En esta y otras apli-
caciones surgen problemas de optimizacin geomtrica derivados de la existencia
de diferentes triangulaciones de un conjunto de puntos.
Una condicin deseable para la que podramos calicar de buena triangu-
lacin es que sus tringulos sean, si no regulares, s lo ms regulares posible. Es
claro que si podemos disponer los puntos a nuestro gusto en el plano, podremos
conseguir nuestro objetivo de obtener tringulos regulares sin ms que disponer-
los en los vrtices de una malla triangular regular. Pero, en ocasiones, los puntos
que constituyen los vrtices de la triangulacin no son variables si no jados de
antemano. En estas condiciones, cul es la triangulacin "ms regular" de esos
puntos?
Dada una triangulacin de n puntos dados, llamemos vector de ngulos de
la triangulacin al vector que tiene como componentes las medidas de todos los
ngulos de todos los tringulos de la triangulacin ordenados de menor a mayor.
Dos triangulaciones de un mismo conjunto de puntos tienen dos vectores de
ngulos de la misma dimensin
5
. Ordenaremos las triangulaciones de un conjunto
3
Se recomienda que los puntos estn en posicin general, es decir, que no haya tres alineados.
4
Este experimento se puede convertir en un juego para dos jugadores: Alternativamente los
jugadores dibujan los segmentos. El ltimo que consigue dibujar uno, gana. Para un matemtico,
que conoce la frmula de Euler, el juego tiene poco inters porque puede conocer de antemano
el resultado. Slo tiene que saber cuntos puntos se han dibujado y cuntos hay en la envolvente
convexa (es un ejercicio para el lector atento que se lee hasta las notas a pi de pgina, el demostrar
la armacin anterior).
Se puede mejorar el juego propuesto de varias maneras para convertirlo en un juego con cierto
inters incluso para un matemtico.
5
De nuevo un ejercicio para el lector atento: Demustrese que la dimensin del vector de
Envolvente convexa, triangulacin de Delaunay, diagrama de Voronoi 163
de puntos empleando el orden lexicogrco de sus vectores de ngulos: diremos
que una triangulacin es mejor que otra si su vector de ngulos es mayor, es decir,
si la primera componente que diere del vector de la otra es mayor.
El orden lexicogrco es una relacin de orden total en R
n
, por lo que en el
conjunto de los vectores de ngulos de las triangulaciones de un conjunto existe un
elemento mximo. A la triangulacin correspondiente se le llama triangulacin
de Delaunay.
Pasemos al problema del clculo de la triangulacin de Delaunay. Para un
matemtico terico, para el que el tiempo fsico no existe, el problema ya est
resuelto. Segn la denicin anterior, no hay mas que hallar todos los vectores de
ngulos de todas las triangulaciones del conjunto y quedarse con la triangulacin
correspondiente al mayor vector. Bien. Aqu se hace necesario acotar inferior-
mente el nmero de triangulaciones que puede tener un conjunto de n puntos. No
es difcil encontrar como cotas funciones exponenciales de n, lo cual de nuevo nos
lleva a la conclusin de que este mtodo, si queremos aplicarlo a un conjunto de
mil puntos (o incluso bastante menores), nos exigira muchos aos de clculo con
el mejor de los ordenadores actuales.
Veamos dos mtodos de clculo mucho ms ecientes: Al primero lo llamare-
mos mtodo del intercambio de aristas y al segundo mtodo de la envolvente
convexa 3D.
Mtodo del intercambio de aristas
El mtodo consta de dos pasos:
Primer paso: hallar una triangulacin cualquiera del conjunto de puntos.
Segundo paso: modicar la triangulacin mejorndola sucesivamente hasta
obtener la triangulacin de Delaunay.
El primer paso no es difcil si disponemos del algoritmo de Graham descrito
antes. En efecto, el algoritmo de Graham proporciona, sin coste adicional, una
triangulacin de los puntos adems del cierre convexo. Para ello basta con dos
ligeras modicaciones: La primera consiste en elegir un punto cualquiera del con-
junto de puntos de entrada como punto para ordenar angularmente los puntos. El
punto puede ser el primero de la lista y podemos incluirlo en la lista nal ordenada
en primer lugar. La segunda modicacin consiste en crear una lista de tringu-
los, que contendr los tringulos de la triangulacin, en la que se incluirn los
siguientes tringulos: De momento todos los tringulos P
1
, P
i
, P
i+1
, para i des-
de 2 hasta n (entendiendo los ndices mdulo n). Adems, durante el proceso del
scan de Graham, se aadirn en la lista los tringulos P
i1
, P
i
, P
i+1
cada vez que se
ngulos no depende de la triangulacin elegida (indicacin: emplese la conocida frmula de Euler
C + V = A + 2).
164 Un Paseo por la Geometra
elimine el punto P
i
debido a que dicho punto resulta interior. La lista de tringulos
resultante es una triangulacin del conjunto de puntos. Como vemos, la compleji-
dad, en trminos de su orden de magnitud, no aumenta respecto del algoritmo de
Graham. Sigue siendo O(n log n).
El segundo paso es ms sencillo an. Se trata de revisar las aristas (segmentos)
de la triangulacin una a una, todas las veces que sea necesario, hasta que no quede
ninguna ilegal. Veamos qu es una arista ilegal y cmo se puede legalizar median-
te un cambio sencillo: Una arista de la triangulacin, si no es de la envolvente
convexa, separa dos tringulos de la triangulacin. Si esos dos tringulos forman
un cuadriltero convexo, la arista ser una de sus dos diagonales. En estas circuns-
tancias diremos que la arista es ilegal si el crculo circunscrito a uno de los dos
tringulos que separa la arista contiene en su interior por completo al otro tringu-
lo. Cualquier otra arista diremos que es legal. Legalizar una arista ilegal consiste
en sustituirla por la otra diagonal del cuadrilatero descrito. Es claro que, salvo que
los cuatro vrtices del cuadriltero sean concclicos, de las dos diagonales de di-
chos cuadrilteros convexos siempre habr una que ser arista legal y otra ilegal.
Tampoco resulta difcil demostrar que al legalizar una arista, cambiando los dos
tringulos correspondientes por los nuevos que se generan, se obtiene una trian-
gulacin con un vector de ngulos mayor, y, por lo tanto una mejor triangulacin
6
.
En consecuencia, partiendo de una triangulacin cualquiera y legalizando una a
una las aristas ilegales, se llega necesariamente al mximo vector de ngulos y su
correspondiente triangulacin: la triangulacin de Delaunay.
Para la validez del algoritmo as como para analizar su complejidad es impor-
tante observar que el proceso de mejora no nos lleva a bucles que podran hacer
que el proceso no termine. En efecto, cada legalizacin de una arista ilegal signi-
ca una mejora estricta de la triangulacin, o, lo que es lo mismo, a un vector de
ngulos estrictamente mayor respecto del orden correspondiente. En consecuencia
el proceso termina necesariamente en un nmero nito de pasos y necesariamente
encontrando la mejor de las triangulaciones, la de Delaunay.
La complejidad en el peor caso es O(n
2
), ya que puede suceder que exista solo
una arista legal en la triangulacin de partida que nos exija revisar todas las aristas
para encontrarla y que genere otra arista ilegal nica al legalizarla para la que de
nuevo necesitaremos revisar la lista completa de arista de nuevo. Este suceso se
puede repetir tantas veces como nmero de aristas interiores tiene la triangulacin,
que son siempre una cantidad lineal. A pesar de ello, y de que existen algoritmos
que calculan la triangulacin de Delaunay con O(n log n) operaciones, el algorit-
mo descrito es muy recomendable por su sencillez, lo que conlleva un cdigo de
programacin sencillo y robusto, y porque en general (en media) la complejidad
6
Para demostrarlo se recomienda hacer uso de las relaciones entre los ngulos exteriores, in-
scritos e interiores a una circunferencia.
Envolvente convexa, triangulacin de Delaunay, diagrama de Voronoi 165
es O(n log n) y no O(n
2
) como la del peor caso.
Mtodo del cierre convexo 3D
No hemos descrito cmo calcular el cierre convexo de puntos en el espacio
tridimensional. Tampoco es el objetivo de esta exposicin. Sin embargo supone-
mos al lector capaz de imaginar cmo es el cierre convexo tridimensional: un
poliedro convexo en el espacio cuyas caras, en general, salvo casos degenerados,
son tringulos.
Supongamos que disponemos de un buen algoritmo para calcular el cierre con-
vexo de puntos en 3D. Veamos cmo con l se puede calcular la triangulacin de
Delaunay de un conjunto de puntos del plano.
En efecto, si ampliamos las coordenadas (x, y) de cada uno de los puntos da-
dos del plano con una tercera coordenada (x, y, x
2
+ y
2
), hemos transformado los
puntos en puntos del espacio situados sobre el paraboloide z = x
2
+ y
2
. Con ello
conseguimos que todos los puntos estn en posicin convexa (todos forman parte
de la envolvente convexa). Adems, y lo que es ms interesante, cada tringulo
de la envolvente inferior del cierre convexo determina un plano que deja todos los
dems puntos por encima de l y que corta al paraboloide en una elipse que se
proyecta en el plano XY en una circunferencia circunscrita a los puntos proyec-
tados de los vrtices del tringulo. El hecho de que los dems puntos estn por
encima del plano, equivale a que la circunferencia proyeccin de la elipse no con-
tenga a ningn punto de los de partida. Esta condicin caracteriza los tringulos
de la triangulacin de Delaunay: tres puntos de un conjunto de puntos del plano
son los vrtices de un tringulo en la triangulacin de Delaunay si, y slo si, el
crculo circunscrito no contiene a ningn punto del conjunto en su interior (aqu
suponemos que no hay cuatro puntos concclicos entre los dados).
En consecuencia, las observaciones anteriores llevan al siguiente resultado sor-
prendente:
La proyeccin de la envolvente convexa inferior de los puntos (x
i
, y
i
, x
2
i
+ y
2
i
)
sobre el plano XY es la triangulacin de Delaunay de los puntos (x
i
, y
i
), i =
1, , n.
En resumen, si disponemos de un algoritmo para calcular cierres convexos en
3D, tenemos adems un algoritmo para calcular triangulaciones de Delaunay en
el plano.
3. Diagramas de Voronoi
Supongamos que, centrados en cada uno de los n puntos del plano que tenemos
como datos de partida, comienzan a crecer crculos a la misma velocidad. Cada
punto se apropia del rea que ocupa el crculo centrado en l siempre que no est
previamente ocupada por otro. Al nal, cuando los radios de los crculos tienden
a innito, Qu regin del plano corresponder a cada uno de los puntos?
166 Un Paseo por la Geometra
y que corta al paraboloide en una elipse que se proyecta en el plano XY en una
circunferencia circunscrita a los puntos proyectados de los vrtices del tringulo. El
hecho de que los dems puntos estn por encima del plano, equivale a que la
circunferencia proyeccin de la elipse no contenga a ningn punto de los de partida.
Esta condicin caracteriza los tringulos de la triangulacin de Delaunay: tres puntos de
un conjunto de puntos del plano son los vrtices de un tringulo en la triangulacin de
Delaunay si, y slo si, el crculo circunscrito no contiene a ningn punto del conjunto en
su interior (aqu suponemos que no hay cuatro puntos concclicos entre los dados).
En consecuencia, las observaciones anteriores llevan al siguiente resultado
sorprendente:
La proyeccin de la envolvente convexa inferior de los puntos (x
i
, y
i
, x
i
2
+y
i
2
) sobre el
plano XY es la triangulacin de Delaunay de los puntos (x
i
, y
i
), i = 1, , n.

En resumen, si disponemos de un algoritmo para calcular cierres convexos en 3D,
tenemos adems un algoritmo para calcular triangulaciones de Delaunay en el plano.


3.- Diagramas de Voronoi

Supongamos que, centrados en cada uno de los n puntos del plano que tenemos como
datos de partida, comienzan a crecer crculos a la misma velocidad. Cada punto se
apropia del rea que ocupa el crculo centrado en l siempre que no est previamente
ocupada por otro. Al final, cuando los radios de los crculos tienden a infinito, Qu
regin del plano corresponder a cada uno de los puntos?





Figura 1 : Proceso de obtencin de un diagrama de Voronoi mediante la expansin de crculos.

En numerosos procesos naturales ocurre un fenmeno de este estilo. De hecho, una
imagen como la de la figura 2 recuerda a la imagen de un tejido celular:

Figura 1: Proceso de obtencin de un diagrama de Voronoi mediante la
expansin de crculos
En numerosos procesos naturales ocurre un fenmeno de este estilo. De hecho,
una imagen como la de la gura 2 recuerda a la imagen de un tejido celular:


Figura 2 : Simulacin de un tejido celular mediante un diagrama de Voronoi.

Es fcil observar que si el conjunto de puntos de partida tiene un solo punto, la regin
que le corresponder ser todo el plano. Si se trata de un conjunto de dos puntos, la
mediatriz de esos puntos ser la frontera que separar las regiones correspondientes a
cada uno. Si se trata de tres puntos no alineados, las fronteras de las regiones las
determinarn tres semirrectas contenidas en las mediatrices de los puntos tomados dos a
dos. En el caso de estar alineados, las fronteras sern las dos de las tres mediatrices, que
sern paralelas. En general, cmo es la regin de uno de los puntos? Se puede observar
que ser la interseccin de n-1 semiplanos, cada uno de los cuales est determinado por
la mediatriz del punto con cada uno de los dems. En consecuencia, la regin de un
punto tiene que ser una regin poligonal convexa como se observa en las figuras 1 y 2.

Cada una de estas regiones se denomina regin de Voronoi del punto correspondiente y
a la particin del plano producida por todas ellas se denomina diagrama de Voronoi.
Los diagramas de Voronoi son estructuras geomtricas muy tiles y han sido
redescubiertas en numerosas ocasiones en diferentes campos cientficos (de ah la
variedad de denominaciones diferentes tambin: polgonos de Thiesen, polgonos de
Dirichlet, zonas de influencia, regiones de proximidad, )

Pues bien, quitmosle esta apariencia tan diferente a las anteriores a esta estructura
geomtrica para descubrir que, en realidad, se trata de la misma que ahora conoce bien
el lector: La triangulacin de Delaunay.

Podemos hacerlo en los dos sentidos: Si partimos de un diagrama de Voronoi, vamos a
descubrir en l una triangulacin de Delaunay. Si partimos de una triangulacin de
Delaunay, veremos que de ella se obtiene de forma muy sencilla un diagrama de
Voronoi.

Si conectamos mediante un segmento rectilneo dos de los puntos si sus
correspondientes regiones de Voronoi comparten parte de su frontera, el resultado ser
la triangulacin de Delaunay de los puntos (lo mismo que ocurre con la triangulacin de
Delaunay, supondremos que no hay cuatro puntos concclicos).
7



7
Ms ejercicios para el lector que siga atento: a) Porqu se obtiene una triangulacin? b) Porqu es
precisamente la triangulacin de Delaunay?
Figura 2: Simulacin de un tejido celular mediante un diagrama de Voronoi
Es fcil observar que si el conjunto de puntos de partida tiene un solo punto,
la regin que le corresponder ser todo el plano. Si se trata de un conjunto de
dos puntos, la mediatriz de esos puntos ser la frontera que separar las regiones
correspondientes a cada uno. Si se trata de tres puntos no alineados, las fronteras
de las regiones las determinarn tres semirrectas contenidas en las mediatrices de
los puntos tomados dos a dos. En el caso de estar alineados, las fronteras sern las
dos de las tres mediatrices, que sern paralelas. En general, cmo es la regin de
uno de los puntos? Se puede observar que ser la interseccin de n1 semiplanos,
cada uno de los cuales est determinado por la mediatriz del punto con cada uno
Envolvente convexa, triangulacin de Delaunay, diagrama de Voronoi 167
de los dems. En consecuencia, la regin de un punto tiene que ser una regin
poligonal convexa como se observa en las guras 1 y 2.
Cada una de estas regiones se denomina regin de Voronoi del punto corres-
pondiente y a la particin del plano producida por todas ellas se denomina diagra-
ma de Voronoi. Los diagramas de Voronoi son estructuras geomtricas muy tiles
y han sido redescubiertas en numerosas ocasiones en diferentes campos cientcos
(de ah la variedad de denominaciones diferentes tambin: polgonos de Thiesen,
polgonos de Dirichlet, zonas de inuencia, regiones de proximidad, ...)
Pues bien, quitmosle esta apariencia tan diferente a las anteriores a esta es-
tructura geomtrica para descubrir que, en realidad, se trata de la misma que ahora
conoce bien el lector: La triangulacin de Delaunay.
Podemos hacerlo en los dos sentidos: Si partimos de un diagrama de Voronoi,
vamos a descubrir en l una triangulacin de Delaunay. Si partimos de una trian-
gulacin de Delaunay, veremos que de ella se obtiene de forma muy sencilla un
diagrama de Voronoi.
Si conectamos mediante un segmento rectilneo dos de los puntos si sus corres-
pondientes regiones de Voronoi comparten parte de su frontera, el resultado ser la
triangulacin de Delaunay de los puntos (lo mismo que ocurre con la triangulacin
de Delaunay, supondremos que no hay cuatro puntos concclicos)
7
.


Figura 3 : Diagrama de Voronoi y su estructura dual, la triangulacin de Delaunay.

A partir de la triangulacin de Delaunay de un conjunto de puntos se puede obtener su
diagrama de Voronoi de la siguiente forma: La regin de un punto la determinan las
mediatrices de ese punto con sus puntos vecinos (los que estn conectados con l por
una arista en la triangulacin de Delaunay). El orden angular de los vecinos determina
el orden en que las mediatrices intervienen formando la frontera de la regin de Voronoi
del punto. Las regiones de los puntos que son vrtices del cierre convexo son no
acotadas y las del resto son polgonos acotados.
8


Esta relacin entre la triangulacin de Delaunay y el diagrama de Voronoi de un
conjunto de puntos es una dualidad punto-regin y arista-arista: En efecto, podemos
asociar a cada vrtice de la triangulacin, que son los puntos del conjunto dado, su
correspondiente regin de Voronoi. De forma anloga, cada tringulo de la
triangulacin se corresponde con su circuncentro, que es precisamente un vrtice del
diagrama de Voronoi. Por su parte, cada arista del diagrama de Voronoi, como hemos
dicho, determina una arista de la triangulacin de Delaunay. Esta dualidad, como
muchas otras, permite resolver problemas diferentes con las mismas tcnicas. A partir
de este descubrimiento, hablar de diagramas de Voronoi o de triangulaciones de
Delaunay, es hablar de la misma estructura en lenguajes diferentes. Las propiedades de
una se transforman en propiedades de la otra.

En resumen, si disponemos de un buen algoritmo para calcular cierres convexos en dos
y tres dimensiones, disponemos de un buen algoritmo para calcular triangulaciones de
Delaunay y diagramas de Voronoi en el plano. Esto justifica el ttulo de la exposicin:
son tres estructuras geomtricas diferentes, pero estrechamente relacionadas entre s.

4.- Aplicaciones

Son numerosas las aplicaciones de los cierres convexos, las triangulaciones de Delaunay
y los diagramas de Voronoi. Aqu vamos a mostrar dos a modo de ejemplo con nimo
de estimular la curiosidad del lector. Si tenemos xito en esto ltimo, estamos seguros
de que el lector sabr encontrar mucha ms informacin y mejor detallada en la red o
incluso generarla por s mismo.

Reconstruccin de curvas

Supongamos que tenemos una muestra de puntos de una curva y hemos perdido la curva
de la que proceden. Ms que una expresin algebraica ms o menos elegante de la

8
Aqu hay de nuevo ms ejercicios para el lector. Suponemos que si ha llegado hasta aqu es porque le
interesa, as que mejor es descubrir las cosas por uno mismo. Es ms estimulante.
Figura 3: Diagrama de Voronoi y su estructura dual, la triangulacin de
Delaunay
A partir de la triangulacin de Delaunay de un conjunto de puntos se puede
obtener su diagrama de Voronoi de la siguiente forma: La regin de un punto
la determinan las mediatrices de ese punto con sus puntos vecinos (los que estn
conectados con l por una arista en la triangulacin de Delaunay). El orden angular
de los vecinos determina el orden en que las mediatrices intervienen formando la
7
Ms ejercicios para el lector que siga atento: a) Porqu se obtiene una triangulacin? b)
Porqu es precisamente la triangulacin de Delaunay?.
168 Un Paseo por la Geometra
frontera de la regin de Voronoi del punto. Las regiones de los puntos que son
vrtices del cierre convexo son no acotadas y las del resto son polgonos acotados
8
.
Esta relacin entre la triangulacin de Delaunay y el diagrama de Voronoi
de un conjunto de puntos es una dualidad punto-regin y arista-arista: En efecto,
podemos asociar a cada vrtice de la triangulacin, que son los puntos del conjunto
dado, su correspondiente regin de Voronoi. De forma anloga, cada tringulo de
la triangulacin se corresponde con su circuncentro, que es precisamente un vr-
tice del diagrama de Voronoi. Por su parte, cada arista del diagrama de Voronoi,
como hemos dicho, determina una arista de la triangulacin de Delaunay. Esta
dualidad, como muchas otras, permite resolver problemas diferentes con las mis-
mas tcnicas. A partir de este descubrimiento, hablar de diagramas de Voronoi
o de triangulaciones de Delaunay, es hablar de la misma estructura en lenguajes
diferentes. Las propiedades de una se transforman en propiedades de la otra.
En resumen, si disponemos de un buen algoritmo para calcular cierres con-
vexos en dos y tres dimensiones, disponemos de un buen algoritmo para calcular
triangulaciones de Delaunay y diagramas de Voronoi en el plano. Esto justica
el ttulo de la exposicin: son tres estructuras geomtricas diferentes, pero es-
trechamente relacionadas entre s.
4. Aplicaciones
Son numerosas las aplicaciones de los cierres convexos, las triangulaciones de De-
launay y los diagramas de Voronoi. Aqu vamos a mostrar dos a modo de ejemplo
con nimo de estimular la curiosidad del lector. Si tenemos xito en esto ltimo,
estamos seguros de que el lector sabr encontrar mucha ms informacin y mejor
detallada en la red o incluso generarla por s mismo.
Reconstruccin de curvas
Supongamos que tenemos una muestra de puntos de una curva y hemos per-
dido la curva de la que proceden. Ms que una expresin algebraica ms o menos
elegante de la ecuacin de la curva, nos interesa recuperar su topologa. Por ello
nos basta en realidad saber o descubrir en qu orden aparecen los puntos en la
curva, y cules son las componentes y ramicaciones de la misma. Sabido esto,
podemos conectar los puntos formando poligonales que darn una idea aproxi-
mada de la curva de la que proceden. La idea bsica que subyace es que debemos
conectar puntos prximos entre s, y no conectar puntos que no sean relativamente
prximos. En la gura 4 se muestra un ejemplo de lo que se pretende hacer em-
pleando para ello un algoritmo que lo haga de forma automtica. Se quiere que los
puntos dados se conecten obteniendo el nmero 50 del que proceden. De hecho,
el diseo del numero 50 se realiz a mano y no se corresponde, por tanto, con
8
Aqu hay de nuevo ms ejercicios para el lector. Suponemos que si ha llegado hasta aqu es
porque le interesa, as que mejor es descubrir las cosas por uno mismo. Es ms estimulante.
Envolvente convexa, triangulacin de Delaunay, diagrama de Voronoi 169
ninguna curva de ecuaciones predeterminadas.
ecuacin de la curva, nos interesa recuperar su topologa. Por ello nos basta en realidad
saber o descubrir en qu orden aparecen los puntos en la curva, y cules son las
componentes y ramificaciones de la misma. Sabido esto, podemos conectar los puntos
formando poligonales que darn una idea aproximada de la curva de la que proceden.
La idea bsica que subyace es que debemos conectar puntos prximos entre s, y no
conectar puntos que no sean relativamente prximos. En la figura 4 se muestra un
ejemplo de lo que se pretende hacer empleando para ello un algoritmo que lo haga de
forma automtica. Se quiere que los puntos dados se conecten obteniendo el nmero 50
del que proceden. De hecho, el diseo del numero 50 se realiz a mano y no se
corresponde, por tanto, con ninguna curva de ecuaciones predeterminadas.



Figura 4 : Muestra de puntos tomados de una curva y su reconstruccin mediante el algoritmo crust.


Este problema se enmarca dentro de los problemas conocidos como problemas de
reconstruccin. Existen mltiples versiones de este tipo de problemas y con diferentes
condiciones tanto en los datos como en el objeto que se desea obtener a partir de ellos.
Para el caso propuesto existe una buena solucin basada en el diagrama de Voronoi y la
triangulacin de Delaunay de los puntos, siempre que la muestra de puntos sea buena,
lo que esencialmente significa que sea suficientemente densa y uniforme (para explicar
esto el dicho andaluz viene muy bien: Lo que no puede ser, no puede ser, y adems es
imposible, que equivale a de donde no hay, no se puede sacar).

La idea original fue de Nina Amenta et al. [1] quienes llamaron al resultado de su
algoritmo crust (corteza). Posteriormente, Gold et al. [5] modificaron el algoritmo
para obtener el mismo resultado de forma ms sencilla y eficiente. Esta es la idea del
clculo del crust en la versin de Gold: El crust est formado por las aristas de la
triangulacin de Delaunay de los puntos que verifiquen la siguiente condicin: Son
aristas que se cortan con su arista dual del diagrama de Voronoi y adems, los crculos
que pasan por los extremos de la arista Delaunay y cada uno de los extremos de su arista
dual no contienen ningn punto del conjunto original en su interior.

Los resultados de este algoritmo, para muestras buenas, como se ha mencionado, son
espectaculares. Por otra parte, el algoritmo es bien sencillo. Su parte ms complicada
consiste en calcular la triangulacin de Delaunay y el diagrama de Voronoi del conjunto
de puntos dado.



Figura 4: Muestra de puntos tomados de una curva y su reconstruccin mediante
el algoritmo "crust"
Este problema se enmarca dentro de los problemas conocidos como problemas
de reconstruccin. Existen mltiples versiones de este tipo de problemas y con
diferentes condiciones tanto en los datos como en el objeto que se desea obtener
a partir de ellos. Para el caso propuesto existe una buena solucin basada en el
diagrama de Voronoi y la triangulacin de Delaunay de los puntos, siempre que la
muestra de puntos sea buena, lo que esencialmente signica que sea suciente-
mente densa y uniforme (para explicar esto el dicho andaluz viene muy bien: "Lo
que no puede ser, no puede ser, y adems es imposible", que equivale a "de donde
no hay, no se puede sacar").
La idea original fue de Nina Amenta et al. [1] quienes llamaron al resultado
de su algoritmo "crust" (corteza). Posteriormente, Gold et al. [5] modicaron el
algoritmo para obtener el mismo resultado de forma ms sencilla y eciente. Esta
es la idea del clculo del crust en la versin de Gold: el crust est formado por las
aristas de la triangulacin de Delaunay de los puntos que veriquen la siguiente
condicin: son aristas que se cortan con su arista dual del diagrama de Voronoi y
adems, los crculos que pasan por los extremos de la arista Delaunay y cada uno
de los extremos de su arista dual no contienen ningn punto del conjunto original
en su interior.
Los resultados de este algoritmo, para muestras buenas, como se ha menciona-
do, son espectaculares. Por otra parte, el algoritmo es bien sencillo. Su parte ms
complicada consiste en calcular la triangulacin de Delaunay y el diagrama de
Voronoi del conjunto de puntos dado.
Estadstica: anlisis de centralidad
En el anlisis de datos multiparamtricos juega un papel importante el estudio
de la profundidad y la centralidad de los datos. La idea de profundidad de un
punto respecto a la muestra a la que pertenece se puede denir de varias formas,
170 Un Paseo por la Geometra
pero en todas ellas se quiere recoger la idea de cun interno es un dato dentro
de la muestra. Un dato con gran profundidad se dice que es un dato central y se
considera un buen representante de la muestra.
Una de las deniciones clsicas de profundidad se basa en las envolventes
convexas de un conjunto. Los puntos que pertenecen a la envolvente convexa se
consideran exteriores y se dice que tienen profundidad cero. Si se suprimen de
la muestra los puntos exteriores, los puntos exteriores del conjunto resultante se
dice que son de profundidad dos. Iterando el proceso se denen los puntos de
profundidad i como los puntos exteriores del conjunto resultante de eliminar de
la muestra los puntos de profundidad menor a i. La profundidad de la muestra
se dene como la mxima profundidad de sus puntos. Las sucesivas envolventes
convexas que denen la profundidad de los puntos de una muestra se denominan
capas convexas y se pueden calcular empleando cualquiera de los algoritmos de
clculo de envolventes convexas. Si se emplea el algoritmo de Graham descrito
antes, como el nmero de capas convexas puede ser lineal respecto del nmero de
puntos, la complejidad total del mtodo ser de orden O(n
2
logn). Con el algoritmo
de Jarvis se obtiene un resultado mejor, pues emplea un tiempo lineal por cada
punto, por lo que la complejidad total para hallar las capas convexas es O(n
2
).
Existe un algoritmo de Chazelle [4] que calcula todas las capas convexas de n
puntos del plano con complejidad O(n log n).
Estadstica: anlisis de centralidad.

En el anlisis de datos multiparamtricos juega un papel importante el estudio de la
profundidad y la centralidad de los datos. La idea de profundidad de un punto respecto a
la muestra a la que pertenece se puede definir de varias formas, pero en todas ellas se
quiere recoger la idea de cun interno es un dato dentro de la muestra. Un dato con gran
profundidad se dice que es un dato central y se considera un buen representante de la
muestra.

Una de las definiciones clsicas de profundidad se basa en las envolventes convexas de
un conjunto. Los puntos que pertenecen a la envolvente convexa se consideran
exteriores y se dice que tienen profundidad cero. Si se suprimen de la muestra los
puntos exteriores, los puntos exteriores del conjunto resultante se dice que son de
profundidad dos. Iterando el proceso se definen los puntos de profundidad i como los
puntos exteriores del conjunto resultante de eliminar de la muestra los puntos de
profundidad menor a i. La profundidad de la muestra se define como la mxima
profundidad de sus puntos. Las sucesivas envolventes convexas que definen la
profundidad de los puntos de una muestra se denominan capas convexas y se pueden
calcular empleando cualquiera de los algoritmos de clculo de envolventes convexas. Si
se emplea el algoritmo de Graham descrito antes, como el nmero de capas convexas
puede ser lineal respecto del nmero de puntos, la complejidad total del mtodo ser de
orden O(n
2
log n). Con el algoritmo de J arvis se obtiene un resultado mejor, pues
emplea un tiempo lineal por cada punto, por lo que la complejidad total para hallar las
capas convexas es O(n
2
). Existe un algoritmo de Chazelle [4] que calcula todas las
capas convexas de n puntos del plano con complejidad O(n log n).



Figura 5 : Una muestra de datos biparamtricos, sus capas convexas y sus capas Delaunay. Las capas
Delaunay son ms adecuadas si se quieren tener en cuenta posibles agrupaciones de los datos.

Figura 5: Una muestra de datos biparamtricos, sus capas convexas y sus capas
Delaunay. Las capas Delaunay son ms adecuadas si se quieren tener en cuenta
posibles agrupaciones de los datos
Envolvente convexa, triangulacin de Delaunay, diagrama de Voronoi 171
La idea de ir quitando las capas de la muestra (algunos lo llaman "pelar la
cebolla" - "onion peeling") para denir la profundidad de los puntos se puede
aplicar empleando otras estructuras. En particular la triangulacin de Delaunay: a
los puntos de la envolvente convexa se les asigna profundidad cero, como antes. A
los puntos que estn conectados a stos mediante una arista en la triangulacin de
Delaunay y no son de profundidad cero, se les asigna profundidad uno. Iterando el
proceso, a los puntos conectados mediante una arista con los de profundidad i que
no tienen profundidad asignada menor o igual a i, se les asigna la profundidad i+1.
Si en la triangulacin de Delaunay se conservan las aristas que conectan puntos
de la misma profundidad eliminando el resto, se obtiene una estructura de capas
como se muestra en la gura 5. Esta forma de denir las capas de una muestra
tiene, sobre la de las capas convexas, la ventaja de que recoge la informacin
sobre posibles agrupaciones de los datos (clustering).
5. Conclusin
Envolventes convexas, triangulaciones de Delaunay y diagramas de Voronoi
son estructuras geomtricas de gran utilidad asociadas a un conjunto de puntos.
Como se ha visto, las tres estructuras estn ntimamente relacionadas, pudiendo
obtenerse una de otra con un nmero de operaciones proporcional al tamao del
conjunto de puntos. Esta condicin es la que hace que, bajo el punto de vista de la
algortmica, se consideren estructuras equivalentes. Han sido y son uno de los cen-
tros de atencin en el desarrollo de la Geometra computacional. Al lector intere-
sado le recomiendo la lectura del libro de Marc de Berg et al. [3] en el que se hace
una muy buena introduccin a estas tres estructuras as como a la Geometra com-
putacional y sus aplicaciones en general. Dos buenas referencias sobre diagramas
de Voronoi son el artculo de Aurenhammer et al. [2] y el libro de Okabe et al [8].
En la red hay mucha informacin disponible, incluidas numerosas aplicaciones
informticas (programas) que permiten obtener las tres estructuras mencionadas y
conocer el funcionamiento de los correspondientes algoritmos (hgase en Google
la bsqueda con las palabras clave: "Voronoi", "Convex hull", "Delaunay". Si a
cualquiera de ellas se aade la palabra "applet", se encontrarn programas como
los mencionados).
Bibliografa
[1] N. Amenta, M. W. Bern, D. Eppstein, The Crust and the beta-Skeleton: Com-
binatorial Curve Reconstruction, Graphical Models and Image Processing 60(2),
125-135, 1998.
[2] F. Aurenhammer, R. Klein, Voronoi diagrams, J. Sack and J. Urrutia, edi-
tores, Handbook of Computational Geometry, Chapter V, 201-290. Elsevier Scien-
172 Un Paseo por la Geometra
ce Publishing, 2000.
[3] M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Computational
Geometry, Algorithms and Applications, Springer, 1997.
[4] B. Chazelle, On the convex layers of a planar set, IEEE Trans. Inform. Theory,
IT-31:509-517, 1985.
[5] C. M. Gold, Crust and anti-crust: a one-step boundary and skeleton extraction
algorithm, Proc. 15th Symp. Computational Geometry, ACM, Jun pp. 189-196,
1999.
[6] R. Graham, An Ecient Algorithm for Determining the Convex Hull of a Finite
Point Set, Info. Proc. Letters 1, 132-133, 1972.
[7] R.A. Jarvis, On the Identication of the Convex Hull of of a Finite Set of Points
in the Plane, Info. Proc. Letters 2, 18-21, 1973.
[8] A. Okabe, B. Boots, K. Sugihara, S. Chiu, Spatial Tessellations - Concepts
and Applications of Voronoi Diagrams, (2nd ed.), Wiley, 2000.
Manuel Abellanas Oar
Universidad Politcnica de Madrid
Facultad de Informtica
Departamento de Matemtica Aplicada
Boadilla del Monte 28660 (Madrid)
e-mail: mabellanas@.upm.es
http://www.dma..upm.es/mabellanas