Una subdivisión del espacio en regiones (celdas) alrededor de un conjunto de puntos semilla tal que cada región contiene todos los puntos más cercanos a su semilla que a cualquier otra, produciendo una teselación usada para análisis de proximidad y consultas de vecino más cercano.

Principio

La celda de Voronoi para una semilla es la intersección de semiespacios determinados por las mediatrices perpendiculares entre esa semilla y cada otra; la colección de celdas cubre el dominio con regiones convexas (en entornos euclídeos) cuya adyacencia codifica relaciones de vecino más cercano.

Demostración

Dadas semillas S = {s1,s2,...,sn} en el plano, la celda de si es {x | dist(x,si) ≤ dist(x,sj) para todo j}; por ejemplo, calcular las mediatrices perpendiculares entre semillas cercanas genera celdas poligonales cuyos vértices son circuncentros de triángulos de Delaunay.

Aplicación incorrecta

Usar diagramas de Voronoi con una métrica inapropiada sin adaptar la construcción de bisectrices o aplicar propiedades euclídeas estándar (convexidad, bisectrices rectas) en contextos no euclídeos puede producir celdas incorrectas y una información de proximidad engañosa.

Consecuencia

Los diagramas de Voronoi proporcionan un índice espacial canónico para la búsqueda del vecino más cercano, regiones de influencia y clustering espacial; su dual, la triangulación de Delaunay, apoya la generación de mallas y consultas geométricas eficientes.

Inversión

Revertir la perspectiva da la triangulación de Delaunay, que conecta semillas en simpléctices cuyos circuncentros forman los vértices de Voronoi; esta inversión cambia el foco de la propiedad de región a la conectividad simpléctial.

Límite

Definido para semillas discretas en espacios métricos donde las distancias y las bisectrices están bien definidas; en espacios euclídeos las celdas son politopos convexos, mientras que en métricas ponderadas, anisotrópicas o no euclídeas las celdas pueden ser no convexas o tener estructura más compleja.

Tensión semántica

Las particiones de Voronoi a veces se confunden con clusters de vecino más cercano o regiones basadas en densidad; a diferencia del clustering probabilístico, las celdas de Voronoi son particiones deterministas inducidas por la métrica y no incorporan la densidad de datos ni suavizado estadístico salvo que se extiendan.

Síntesis

Un diagrama de Voronoi es la partición inducida por la métrica del espacio en regiones propiedad de semillas obtenida al intersectar semiespacios provenientes de bisectrices pares; sus celdas convexas y la dualidad con la triangulación de Delaunay lo convierten en una estructura fundamental para proximidad, indexación espacial y algoritmos geométricos.