Diagrama de Voronoi

Hoy vamos a hablar de los diagramas de Voronoi que debe ser una de las herramientas matemáticas más versátiles después de la suma y la resta. Para definir un diagrama de Voronoi lo primero que nos hace falta es un conjunto de puntos, las regiones de Voronoi de un conjunto de puntos son las regiones que están más cerca a uno de los puntos que a cualquiera de los otros puntos. Por ejemplo si tuviéramos solo 2 puntos en el plano Euclideo en 2 dimensiones entonces la recta equidistante a los 2 puntos estaría limitando cada una de las regiones . Veamos un ejemplo un poco más complicado (10 puntos) hecho con el Mathematica.

Diagrama de voronoi de 10 puntos aleatorios

Diagrama de voronoi de 10 puntos aleatorios

Se puede comprobar que el segmento de linea que separa 2 regiones es un segmento equidistante a 2 puntos y los vértices son equidistantes a 3 puntos (esto se da en el caso en el que no haya degeneración, como cuando los puntos se eligen aleatoriamente, de forma manual se puede conseguir que se cumplan otras relaciones, pero lo que nos va a interesar por ahora son los casos sin degeneraciones). Después de haber hecho esta pequeña introducción voy a dar una definición más formal (matemática) de un diagrama de Voronoi, espero que nadie se asuste, solo lo doy por completitud, se puede seguir perfectamente el artículo sin esa parte.

VD =\textrm{ Diagrama de Voronoi}\\P = \textrm{ Conjunto de puntos}  \\R_i =\textrm{ Region del punto } p_i  = \{x\in\mathbb{R}^2 : d(x,p_i) < d(x,p_j) \forall j \neq i\}\\\bar{R_i} =\textrm{ Frontera de } R_i\\  VD = \{R_i\forall i\}\cup\{\bar{R_i} \forall i\}\cup\{\bar{R_i}\cap\bar{R_j}\neq \emptyset \forall i, j : i\neq j\}\cup\{\bar{R_i}\cap\bar{R_j}\cap\bar{R_k}\neq \emptyset \forall i, j, k : i\neq j\ \textrm{ y } j \neq k \textrm { y }i \neq k\}

Después de esta pequeña introducción veamos algunas utilidades de los diagramas de Voronoi, por ejemplo en meteorología se puede tomar datos de la humedad de un monte, estas medidas aunque se hagan cada metro o cada cm son medidas puntuales, si lo que interesa es aproximar la humedad en toda la región entonces considerar las regiones
del diagrama de Voronoi de donde se han tomado las medidas y asignar la humedad de esa región a la del punto sería una buena aproximación (aún mejor cuanto más medidas se tomen, luego se podrían aplicar métodos para suavizar la función y que fuera continua y se mejoraría en precisión)

También se puede usar para distribución de recursos, por ejemplo supongamos  una ciudad con cada 5 hospitales, esta claro que a cada casa le va a corresponder el hospital más cercano, pero lo que no va a pasar es que vaya un tipo por ahí haciendo el recorrido desde cada casa a los hospitales para ver cual es el más cercano.

Los diagramas de Voronoi se pueden usar tanto en biología, como física, química,… (yo naturalmente no me se todos los sitios en que se usa, si alguien esta interesado en alguno puede usar google). Para acabar con los ejemplos, dejo la web de diagramas de Voronoi y triangulaciones de Delaunay (las triangulaciones de Delaunay son el dual de los diagramas de Voronoi cuando no hay degeneración, pero esto en cualquier modo esta fuera del propósito de este artículo) del departamento de matemática aplicada de la upm:

http://www.dma.fi.upm.es/docencia/segundociclo/geomcomp/voronoi.html

En la web esa hay un modelo interesante para ver hasta que punto pueden ser útiles los diagramas de Voronoi, que es el de modelización de crecimiento de un bosque, ya que he mencionado ese modelo, voy a hacer algunas puntualizaciones, por si alguien decide mirarlo. Lo primero es que yo he hablado de distancia pero no he especificado si  era la euclidiana o cualquiera, como es evidente se pueden aplicar diagramas de Voronoi con cualquier distancia, según la que convenga en el estudio (lo único que la euclidiana es la que tenemos normalmente en mente), sino recuerdo mal ahí usaban otras distancias.

También quería puntualizar el hecho que yo en los ejemplos me he referido a dimensión 2 (y en un plano), realmente no es un requisito imprescindible se puede usar cualquier espacio métrico o variedad riemanniana. Por ejemplo se pueden usar superficies, donde se use la métrica inducida, por ejemplo en el siguiente dibujo se hace el diagrama de Voronoi de una esfera.

Diagrama de Voronoi en una esfera de 100 puntos arbitrarios

Diagrama de Voronoi en una esfera de 100 puntos arbitrarios

Siguiendo con el caso de la esfera, se puede comprobar que ahora que las líneas que unen 2 vértices ya no son rectas sino arcos de circunferencia, también es importante remarcar que en este caso al ser una superficie finita todas las regiones de Voronoi tienen una superficie finita (no como en el caso de considerar todo el plano euclídeo en el que siempre hay alguna región no delimitada).

También es interesante saber que los diagramas de Voronoi se pueden generalizar para el caso  en el que no se consideran puntos, sino por ejemplo lineas y generar las regiones que son más cercanas a cada una de las lineas. También se pueden hacer diagramas de Voronoi de orden superior (k) que es considerar aquellas regiones que tienen los mismos k puntos más cercanos, es fácil ver que en el caso k=1 origina los diagramas de Voronoi convencionales.

http://www.quantumbattle.com/wp-content/plugins/sociofluid/images/technorati_48.png http://www.quantumbattle.com/wp-content/plugins/sociofluid/images/google_48.png http://www.quantumbattle.com/wp-content/plugins/sociofluid/images/myspace_48.png http://www.quantumbattle.com/wp-content/plugins/sociofluid/images/facebook_48.png http://www.quantumbattle.com/wp-content/plugins/sociofluid/images/twitter_48.png http://www.quantumbattle.com/wp-content/plugins/sociofluid/images/meneame_48.png

5 comments for “Diagrama de Voronoi

  1. dc
    14 junio 2010 at 20:00 pm

    Muy buen post me gusto la descripcion!

  2. Pablo Razdrokin
    19 agosto 2010 at 5:08 am

    Muchas Gracias!

  3. bolyai
    21 septiembre 2010 at 10:32 am

    Me gusto mucho el articulo. Esta realmente interesante.

    Gracias, y animo con la web que tiene una pinta increible!

  4. juan pablo
    14 octubre 2011 at 5:54 am

    Muy bueno el articulo.

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos necesarios están marcados *