NM 3.6Diagramas de Voronoi
Diagramas de Voronoi: sitios, vértices, aristas, celdas. Adición de un sitio a un diagrama de Voronoi ya existente. Interpolación del vecino más próximo. Aplicaciones del problema del "vertido de residuos tóxicos".
Sitios, celdas, aristas y vértices
Dado un conjunto de puntos del plano, llamados sitios, un diagrama de Voronoi divide el plano en tantas regiones (celdas) como sitios haya, de manera que la celda de un sitio P está formada por todos los puntos del plano que están más cerca de P que de cualquier otro sitio. Las fronteras entre dos celdas vecinas son segmentos de la mediatriz del segmento que une sus dos sitios, llamados aristas; los puntos donde se encuentran tres (o más) aristas se llaman vértices del diagrama.
Figura 9. Diagrama de Voronoi: cada celda agrupa los puntos más próximos a su sitio.
En los exámenes se dan las coordenadas de los sitios y se pide calcular la ecuación de una o varias mediatrices (las fronteras entre celdas) con el método visto en NM 3.5; no es necesario dibujar a mano el diagrama completo. Para toda la celda de un sitio se supone que el valor de una magnitud asociada (por ejemplo, la pluviosidad registrada en una estación meteorológica) es el mismo que el del sitio: esto es precisamente la interpolación del vecino más próximo.
Construcción de las fronteras de una celda
Para hallar las aristas que rodean la celda de un sitio P entre varios sitios dados, se calcula la mediatriz de P con cada uno de los sitios vecinos; cada mediatriz (o una parte de ella, hasta el vértice donde se cruza con la siguiente) forma uno de los lados de la celda. En los exámenes, el punto que se pide como solución final está siempre en la intersección de tres aristas.
Adición de un nuevo sitio
Al añadir un nuevo sitio Q a un diagrama de Voronoi ya construido, aparece una nueva celda para Q, que "recorta" parte de las celdas de los sitios más próximos a Q: las nuevas fronteras son las mediatrices entre Q y cada uno de esos sitios vecinos, sustituyendo (allí donde correspondan) a parte de las fronteras antiguas.
El problema del "vertido de residuos tóxicos"
Un planteamiento habitual consiste en situar varios sitios (por ejemplo, núcleos de población) y preguntar dónde debería ubicarse una instalación no deseada (un vertedero de residuos tóxicos) para quedar lo más alejada posible de todos ellos. El punto que maximiza la distancia mínima a todos los sitios es siempre un vértice del diagrama de Voronoi (la intersección de varias mediatrices), ya que en cualquier otro punto de una celda siempre se puede uno alejar algo más del sitio correspondiente desplazándose hacia el vértice.
Actividad resuelta
Tres estaciones meteorológicas están situadas en los puntos , y . Un cuarto punto, , queda dentro del diagrama de Voronoi de estos tres sitios. Determina qué estación meteorológica se usaría para estimar la pluviosidad en D, según la interpolación del vecino más próximo.
Solución: se calcula la distancia de D a cada sitio: ; ... se recalcula: ; . Como DC es la menor de las tres distancias, D está en la celda de C, por lo que se le asignaría el valor de pluviosidad registrado en la estación C.
Figura 10. Diagrama de Voronoi de A, B y C: D está en la celda de C.
🖩 Recursos tecnológicos
Calculadora CASIO fx-CG50
Para obtener las coordenadas de un vértice del diagrama de Voronoi (punto equidistante de tres sitios), basta resolver el sistema formado por las ecuaciones de dos mediatrices: en MENU → EQUA → F1 (SIMLT) con 2 incógnitas, o dibujando ambas rectas en MENU → GRAPH y utilizando SHIFT+F5 (G-Solv) → ISCT. Aunque el diagrama completo no se exige construirlo a mano, puede resultar útil representarlo con software de geometría dinámica (como GeoGebra) para visualizar las celdas, las aristas y los vértices antes de resolver el problema analíticamente.
✎ Problemas para practicar en clase
Ejercicios básicos para afianzar la teoría de este ítem. Resuélvelos en tu cuaderno.
1. Dibuja en la cuadrícula los puntos y y construye su diagrama de Voronoi. Indica la ecuación de la arista.
Ver solución
M = (3, 2) ; m_AB = 1/2 ⇒ arista: y − 2 = −2(x − 3) ⇒ y = −2x + 8. Cada región contiene los puntos más cercanos a su sitio
2. Dados los sitios , y , halla las ecuaciones de las tres mediatrices y el vértice de Voronoi.
Ver solución
AB: x = 3 ; AC: y = −x/2 + 15/4 ; BC: y = x/2 + 3/4. Vértice de Voronoi: (3; 2,25)
3. En un diagrama de Voronoi de tres sitios, ¿qué propiedad cumple el vértice respecto de los tres sitios? ¿Qué puede decirse de los puntos situados en una arista?
Ver solución
El vértice equidista de los tres sitios (es el centro de la circunferencia que pasa por ellos). Cada punto de una arista equidista de los dos sitios que separa y está más lejos de los demás
4. Tres centros de salud están en , y . Una persona vive en . ¿Cuál es el centro más cercano? Compruébalo calculando distancias.
Ver solución
d(P, A) = √5 ≈ 2,24 ; d(P, B) = √29 ≈ 5,39 ; d(P, C) = √13 ≈ 3,61. El centro más cercano es A
5. Se quiere abrir una nueva tienda en el vértice de Voronoi de tres tiendas ya existentes. Explica con tus palabras por qué ese punto es el más alejado posible de todas ellas (localmente) y para qué sirve.
Ver solución
El vértice es el punto equidistante de los tres sitios; al alejarse de él en cualquier dirección se acerca a alguna tienda, así que es un máximo local de la distancia a la tienda más cercana. Sirve para situar una nueva tienda lo más lejos posible de la competencia