Diagrama de Voronoi

¿Cómo se construye un diagrama de Voronoi?

Dado un conjunto finito de puntos S = {p₁, p₂, ..., pₙ} en el plano (llamados sitios o generadores), el diagrama de Voronoi divide el plano en regiones, una por cada sitio. La región V(pᵢ) asociada al sitio pᵢ se define como:

V(pᵢ) = { x ∈ ℝ² : d(x, pᵢ) ≤ d(x, pⱼ) ∀ j ≠ i }

Construcción geométrica básica

Para cada par de sitios pᵢ y pⱼ, la mediatriz (perpendicular al segmento que los une por su punto medio) divide el plano en dos semiplanos: los puntos más cercanos a pᵢ y los más cercanos a pⱼ. La celda de Voronoi de pᵢ es la intersección de todos los semiplanos que contienen a pᵢ:

V(pᵢ) = ∩ⱼ≠ᵢ H(pᵢ, pⱼ)

Esta intersección de semiplanos es siempre un polígono convexo (posiblemente no acotado en los bordes).

Algoritmos clásicos

• Fuerza bruta (lo que hace esta app por simplicidad visual): para cada píxel, calcular el sitio más cercano. Complejidad O(n·k) donde k es el número de píxeles. Sirve para visualizar pero es ineficiente.
• Algoritmo de Fortune (1987): usa una "línea de barrido" (sweep line) y una estructura llamada parábola de playa. Complejidad O(n log n), óptimo.
• Divide y vencerás (Shamos y Hoey, 1975): divide los sitios en dos mitades, calcula Voronoi recursivamente y los une. También O(n log n).
• Vía triangulación de Delaunay: el diagrama de Voronoi es el dual geométrico de la triangulación de Delaunay. Calcular una da la otra.

Propiedades importantes

• Cada celda es un polígono convexo.
• Las aristas son segmentos de mediatrices entre pares de sitios.
• Los vértices son equidistantes a 3 o más sitios (centros de circunferencias circunscritas).
• Para n sitios en posición general: a lo sumo 2n - 5 vértices y 3n - 6 aristas.

Métricas alternativas

Cambiando la función de distancia, las celdas cambian de forma:

• Euclídea (√((x₁-x₂)² + (y₁-y₂)²)): celdas con aristas rectas, el caso clásico.
• Manhattan (|x₁-x₂| + |y₁-y₂|): celdas con aristas a 45° y 90°, útil en redes urbanas tipo cuadrícula.
• Chebyshev (max(|x₁-x₂|, |y₁-y₂|)): celdas con aristas horizontales, verticales y a 45°, usada en ajedrez (movimientos del rey).

Aplicaciones

• GIS y planificación urbana: áreas de influencia (escuelas, hospitales, estaciones de servicio).
• Análisis espacial: interpolación por vecino natural, estimación de densidades.
• Telecomunicaciones: cobertura de antenas celulares.
• Robótica: planificación de trayectorias (caminos que maximizan distancia a obstáculos).
• Biología: modelado de territorios animales, estructuras celulares.
• Meteorología: método de polígonos de Thiessen para estimar precipitación a partir de estaciones.
• Astronomía: análisis de distribución de galaxias.

Dato curioso histórico

Aunque llevan el nombre de Georgy Voronoi (matemático ucraniano, 1908), John Snow ya había usado un diagrama equivalente en 1854 para rastrear el brote de cólera en Londres, demostrando que las muertes se concentraban alrededor de la bomba de agua de Broad Street. Es considerado uno de los primeros usos del análisis espacial epidemiológico.