Celdas de Voronoi

Para una triangulación dada, se puede hallar el diagrama dual trazando las mediatrices de cada uno de los lados de los triángulos. En el caso de la triangulación de Delaunay, la malla dual resulta ser el diagrama de Voronoi, de enorme importancia^3.3. Por la propia definición, los nodos de esta malla son los circuncentros de los triángulos de Delaunay. La propiedad más famosa de esta teselación es la siguiente:

La celda de Voronoi correspondiente a un nodo es lugar geométrico de puntos que están más cerca del nodo que de otros nodos.

La simplicidad de este concepto explica lo antiguo que en realidad. Aunque se adjudica su definición precisa a G. Voronoı^3.4, quien introdujo el concepto formalmente (aunque en una red periódica) en 1907, en realidad existía una definición precisa en un trabajo de Dirichlet de 1850. La idea aparece, más informal, ya en la teoría de los vórtices de Descartes (1644).

Su generalidad confiere a este diagrama su importancia en ámbitos muy diversos:

• Asignación de recursos por zonas geográficas (centrales de bomberos, delegaciones de correos, hospitales ...)
• Demarcaciones de animales territoriales.
• En física del estado cristalino son de gran importancia, aunque en el espacio recíproco (de Fourier); las celdas se denominan de Wigner-Seitz.

Es interesante que en muchos de estos ámbitos el concepto haya sido ``redescubierto'' de cero.

A pesar de la mayor simplicidad de la definición del diagrama de Voronoi, en muchos casos es más sencillo implementar una triangulación de Delaunay y calcular las propiedades del diagrama de Voronoi a partir de ella.