Diagramas de Voronoi - dagoquevedo/parallelr GitHub Wiki

Los diagramas de Voronoi [1,2] se encuentran entre las más importantes estructuras en la geometría computacional, este codifica la información de proximidad entre los elementos. Sea un conjunto de puntos en el plano (o en cualquier espacio -dimensional), los cuales llamaremos celda. Definimos como , la celda de Voronoi para , como el conjunto de puntos en el plano que están más cerca de que de cualquier otro sitio. Es decir la celda de Voronoi se define por

,

donde denota la distancia euclídea entre los puntos y . Si bien el diagrama de Voronoi puede definirse sobre cualquier métrica y en cualquier dimensión, en esta práctica nos enfocaremos en el caso planar y Euclidiano, donde se representará la zona por una matriz y las coordenadas serán entonces números enteros en .

El objetivo principal de esta práctica es el análisis sistemático del efecto que el número de semillas y el tamaño de la zona tienen en la distribución de los largos de las grietas. Adicional a lo anterior:

1. Esparcir las semillas con otra distribuciones probabilística y examinar el efecto que tiene cada una de ellas en la asignación de las celdas.
2. Lograr el efecto de crecimiento de las celdas alrededor de las semillas que aparecen en distintos momentos y examinar los cambios producidos en el fenómeno de propagación de grietas.

El siguiente segmento de código [3] codificado en R, es la función que define la celda de Voronoi para cada celda , definida en este caso por el parámetro pos:

cell =  function(pos) {
    row = floor((pos - 1) / n) + 1
    col = ((pos - 1) %% n) + 1
    if (zone[row, col] > 0) {
        return(zone[row, col])
    } else {
        near = 0
        dmin = n * sqrt(2)
        for (seed in 1:k) {
            dx 	 = col - x[seed]
            dy 	 = row - y[seed]
            dist = sqrt(dx^2 + dy^2)
            if (dist < dmin) {
                near = seed
                dmin = dist
            }
        }
        return(near)
    }
}

A continuación se establecen las condiciones de diseño y definición de experimentos para satisfacer los objetivos y analizar los resultados de esta práctica.

• Para analizar el efecto del número de semillas y el tamaño de la zona dada por , se establece entonces tamaños de discretizado a 50 unidades y discretizado a 4 unidades. El experimento es entonces una serie de ejecuciones con las posibles combinaciones de los conjuntos discretizados y cómo parámetros. Se realiza un análisis estadístico para reafirmar las conclusiones empíricas.

• Se utilizan tres distribuciones probabilísticas para esparcir las semillas en el plano cartesiano: (a), Distribución de Poisson con un . (b) Distribución Binomial con un tamaño , y una probabilidad , (c) Distribución normal, la cual queda implicita con el uso de la función sample. Se realiza una única ejecución por cada distribución con y .

• Para lograr el efecto de crecimiento de las celdas alrededor de las semillas se modifica la definición de la celda de Voronoi de tal manera que contemple un radio para cada semilla por lo que cada que estén dentro de este radio se asigne a una semilla . se realiza una única ejecución con y . La celda de Voronoi se define ahora como sigue

.

Se hace uso de una instancia SO Linux (Ubuntu 16.04) 64-bits, con procesador Intel (R) Core (TM) i7-5600U CPU @ 2.60 GHz y 12 GB de memoria RAM con 2 núcleos y 4 procesadores lógicos. La aplicación se ha codificado en R, haciendo uso del paquete doParallel [4] que incluye la función foreach.

La Figura 1 muestra la comparación del tamaño de las grietas generadas para cada combinación . Se observa que el tamaño de la matriz si tiene un efecto en el tamaño de las grietas más no así el número de semillas distribuidas, en este caso bajo una distribución normal.

Figura 1. Comparación de largo de las grietas respecto al tamaño del la matriz y número de semillas.

Para confirmar las conclusiones del análisis gráfico se procede a realizar un análisis estadístico, formulando las siguientes hipótesis alternativas, : El tamaño de la matriz dado por tiene un efecto sobre el tamaño de las grietas. : El número de semillas dado por tiene un efecto sobre el tamaño de las grietas. Bajo la posibilidad de que la distribución de la muestra no cumpla con las condiciones de normalidad, se opta por usar una prueba no paramétrica de Kruskal-Wallis [5]. Se establece un nivel de significancia . La tabla 1 muestra el resultado de este análisis.

Tabla 1. Resultados de la prueba de Kruskal-Wallis

Hipótesis	p-valor
	1.338e-08
	0.3038763

En el caso de la hipótesis alternativa , el p-valor que se obtiene es lo suficientemente menor respecto el nivel de significancia , por lo que se rechaza la hipótesis nula y se acepta la hipótesis alternativa. Por el contrario la hipótesis alternativa se rechaza, al obtener un valor de p-valor mayor al nivel de significancia. Por lo anterior, los resultados estadísticos confirman el análisis gráfico del experimento.

La siguiente imagen muestra la generación de un diagrama de Voronoi con una selección de las semillas bajo una distribución normal en un espacio .

Figura 2. Diagrama de Voronoi con semillas esparcidas bajo una distribución Normal.

La siguiente imagen muestra la generación de un diagrama de Voronoi con una selección de las semillas bajo una distribución de Poisson en un espacio . Se observa como las semillas están distribuidas uniformemente en el área central de la matriz, lo que ocasiona un efecto de embudo en la figura resultante.

Figura 3. Diagrama de Voronoi con semillas esparcidas bajo una distribución de Poisson.

La Figura 4 muestra una animación de crecimiento de las celdas alrededor de las semillas, las cuales aparecen en momentos distintos durante la ejecución.

Figura 4. Diagrama de Voronoi con un crecimiento de las celdas alrededor de las semillas.

A partir de la evidencia empírica y estadística mostrada en los resultados de la generación de diagramas de Voronoi, se concluye lo siguiente:

1. El tamaño de la matriz tiene un efecto en el largo de las grietas. Esto tiene sentido dado que a un mayor espacio en las grietas tienden a tener un mayor espacio de dispersión.

2. El número de semillas no tiene un efecto en el largo de las grietas. Esto puede deberse a que independientemente del número de semillas, se generarán fronteras entre estas, lo que da espacio una potencial propagación de una grieta.

1. M. Berg, O. Cheong, M.V. Kreveld and M. Overmars. Computational Geometry: Algorithms and Applications. Springer, 3ra edición, 2008.
2. E.A. Rodríguez Tello. Diagramas de Voronoi, Notas de clase, Cinvestav, 2013, [url].
3. S.E. Schaeffer. Práctica 4: Diagramas de Voronoi, R paralelo: simulación & análisis de datos, [url].
4. R. Calaway, S. Weston, D. Tenenbaum. Foreach Parallel Adaptor for the 'parallel' Package. R Package, [url].
5. W.H. Kruskal y W.A. Wallis. Use of ranks in one-criterion variance analysis. Journal of the American Statistical Association, 47(260): 583-621, 1952.