Diagramas de Voronoi y triangulación de Delaunay
El diagrama de Voronoi debe su nombre al matemático Gueorgui Voronoi, que fue supervisor de la tesis doctoral de Boris Delaunay en la universidad de San Petersburgo. A su vez, Voronoi fue alumno de Andrei Markov, discípulo de Chebyshev. Estos dos últimos tuvieron gran relevancia en el área de la probabilidad, mientras que los dos primeros la tuvieron en geometría.
De arriba a abajo: Chebyshev, Markov, Voronoi y Delaunay.
Chebyshev
Markov
Voronoi
Delaunay
Dale al botón Play de la animación y disfruta de la belleza y armonía de la geometría, presente en la naturaleza.
Mueve los puntos del siguiente applet y observa cómo cambia el diagrama de Voronoi.
Se han clasificado en dos grupos, rojos y azules, porque la construcción del diagrama de Voronoi se ha hecho mediante el algoritmo "Divide y vencerás" ("Divide and conquer" en inglés).
También puedes ver la triangulación de Delaunay, que tiene muchas aplicaciones y propiedades; por ejemplo, en los gráficos 3D por ordenador, como veremos a continuación. La triangulación de Delaunay de un conjunto de puntos es, por definición, aquella que cumple la condición de que cada circunferencia circunscrita a cada triángulo (de la triangulación) no contiene vértices (de la triangulación) en su interior.
Se puede demostrar que la triangulación de Delaunay se obtiene uniendo el nodo de cada región de Voronoi con los nodos de las regiones vecinas.
Propiedad de la triangulación de Delaunay
De entre todas las triangulaciones posibles de un conjunto dado de puntos del plano, la triangulación de Delaunay maximiza el ángulo mínimo (los ángulos de los triángulos de la triangulación son menos agudos).
Es decir, la triangulación de Delaunay es la más equiangular de entre todas las triangulaciones posibles.
Interpolación en 2D y 3D
Gran importancia tiene la triangulación de Delaunay en la interpolación en 2D y 3D, así como en el diseño de gráficos 3D por ordenador, como se puede inferir.
En la siguiente imagen vemos cómo en la interpolación izquierda hay cuatro puntos negros (prefijados) muy cerca del rojo (uno nuevo adicional) y, sin embargo, no se interpola el rojo mediante ellos, sino mediante otros puntos negros que están mucho más alejados de él. En la interpolación de Delaunay el punto rojo es interpolado por los negros más cercanos a él.
En la imagen posterior podemos observar cómo la triangulación de Delaunay de un paralelogramo escoge la que produce los triángulos más equiláteros (sólo hay dos posibles triangulaciones de este cuadrilátero), y ello trae consigo una mejor interpolación en 3D.
En la última, se fija un conjunto de puntos P = {p1, ..., pn} del plano, pi = (ai, bi, 0). Sea P* = {p*1, ..., p*n} del espacio 3D con p*i = (ai, bi, ai2+bi2),esto es, la proyección vertical de P en el paraboloide z = x2+y2. Entonces la triangulación de Delaunay de P es la proyección ortogonal en el plano z = 0 de la menor envolvente convexa en 3D de P*. Es decir, tres puntos p*i, p*j, p*k forman una cara triangular de la menor envolvente convexa en 3D de P* si, y sólo si, pi, pj, pk forman un triángulo de Delaunay.
