Bueno en este tema, solo les quiero compartir lo que encontre en una pagina de internet, el diagrama de voronoi es sencillo, toda la explicacion viene aqui abajo.
El diagrama de Voronoi es una de las estructuras clásicas en Geometría Computacional (disciplina encargada de resolver problemas geométricos mediante métodos algorítmicos). Es una estructura al tiempo sencilla y poderosa, que parte de una idea tan natural que ha sido descubierta varias veces a lo largo de la historia. De ahí los distintos nombres con los que ha sido conocido: diagrama de Voronoi, polígonos de Thiessen, regiones de Wigner-Seitz, etc.
Pero, ¿qué es el diagrama de Voronoi? Vamos a ilustrarlo con un ejemplo sencillo: supongamos que tenemos una empresa cuya función es ayudar a nuestros clientes a encontrar los servicios más cercanos a su situación actual. Recibimos unas coordenanas por teléfono, web, aplicación móvil... y, en el menor tiempo posible, tenemos que suministrarle la dirección del restaurante, gasolinera, parking, etc. más cercano. ¿Cómo lo hacemos?
Pensemos en el problema de manera geométrica. Partimos de un conjunto de puntos en el plano correspondientes a una categoría de servicios (por ejemplo, gasolineras). Cada consulta de nuestro cliente podemos interpretarla como un nuevo punto que tenemos que emparejar con el más cercano del conjunto inicial. ¿Cómo lo seleccionamos? Fácil, diremos: mido las distancias a cada una de las gasolineras y me quedo con la más pequeña.
Respuesta correcta, pero no del todo. Repetimos las condiciones del problema: tenemos que dar la respuesta en el menor tiempo posible. ¿Cuánto tardamos con este procedimiento? Lo que nos lleve medir la distancia a cada una de las gasolineras. No podemos hacerlo en menos tiempo porque, a priori, no podemos dejar de comprobar ninguna de ellas. ¿Significa esto que éste el mejor método entre todos los posibles?
Pues sí y no. Sí, si sólo vamos a tener unos pocos clientes; pero si esperamos que nuestra empresa sea un éxito (y con lo que nos ha constado montarla pongámonos en el mejor de los casos) y recibir miles de peticiones a cada instante, podemos hacerlo un poco mejor. Y aquí alguien ya habrá dado con la respuesta: en lugar de medir la distancia a cada una de las gasolineras hacemos una partición del plano en regiones, de tal forma que si un punto cae dentro de una determinada región entonces podemos decir cuál es su gasolinera más cercana.
Justamente eso es el diagrama de Voronoi.
O, si queremos una defición más precisa: dado un conjunto S de generadores en el plano, el diagrama de Voronoi de S es la partición del plano tal que a cada punto de S le asigna la región formada por los puntos del plano que están más cerca suya que de cualquier otro elemento de S.
Construir el diagrama no es más rápido que medir la distancia a cada gasolinera. Nada (que funcione) es más rápido que eso. Pero si bien construir el diagrama es más lento, sólo tenemos que hacerlo una vez, y a partir de ahí determinar en qué región está un punto sí puede hacerse antes. Y ahí está el quid de la cuestión. Gastamos un poco más de tiempo al inicio, pero luego nuestras búsquedas serán mucho más rápidas (que es lo que nos exigen nuestros clientes).
Bibliografia:
http://lacanciondemalapata.blogspot.com/2010/02/el-diagrama-de-voronoi-i.html
Nombre: Juan Manuel Casanova Villarreal
Matricula: 1453829
Suscribirse a:
Enviar comentarios (Atom)
7 comentarios:
En tu explicacion del diagrama de voronoi, esta bien, mas no explicaste como hacer un diagrama de voronoi, esto es sencillo al momento de que te den coordenadas, las puedes graficar en un eje cordenado, despues de eso los puntos ke tenemos los dividimos en regiones, las cuales intentamos que esten separadas balanceadamente con el objetivo de que tengan una distancia parecida de un punto a la linea que lo separa.
Al menos eso es lo que entiendo por medio de el diagrama de voronoi, no se si yo este correcto, si no lo estoy me podrias corregir?
Concluyo con lo mismo que dice Hector Tinajero y pues espero que este comentario les pueda servir a los dos.
Bueno esto fue lo que investigue y tengo en mi blog con informacion mas a detalle.
http://karla-ias.blogspot.com
Supongamos que, centrados en cada uno de los n puntos del plano que tenemos como datos de partida, comienzan a crecer círculos a la misma velocidad. Al final, cuando los radios de los círculos tienden
a infinito se forma un diagrama de Voronoi.
Saludos y espero que esto les aya servido
Si,estas en lo correcto, para hacer un diagrama de voronoi puedes hacer una grafica de los puntos que te dan, y mas facil con un applet como el que nos paso la profe puedes poner mas o menos los puntos y ya con eso tienes un bosquejo del diagrama de voronoi, asi vas a ser mas preciso al separar las regiones que haciendolo por tus propios calculos
Gracias por tu aportacion karla, y si me sirvio esa informacion, me pasare a tu blog para verlo en mas detalle.
De nada Juan Manuel, y si de hecho fue lo que yo realise en mi blog utilize el applet para realizar el problema de puntos extras del examen ordianrio y fue mucho mas facil y ya lo que comente en tu blog fue como que una aportacion mas.
Bueno para complementar la información me uviera gustado ver una imágen, concuerdo con mis compañeros karla y hector,
para hacer un diagrama de voronoi puedes hacer una grafica de los puntos que te dan, y mas facil con un applet como el que nos paso la profe puedes poner mas o menos los puntos y ya con eso tienes un bosquejo del diagrama de voronoi, asi vas a ser mas preciso al separar las regiones que haciendolo por tus propios calculos
Gracias...
Muy buena la informacion que obtuviste deja mas en claro como es que los sistemas de informacion telefonicos nos proporcionan el establecimiento mas cercano a nuestra casa o segun lo que estemos buscando para complementar otro ejemplo que encontre yo fue en la climatologia en donde los diagramas de Voronoi se utilizan para calcular la precipitación de un área, basada en una serie de medidas del punto. En este uso, se refieren generalmente como polígonos de Thiessen.
Publicar un comentario