Algoritmo y Diagrama de Voronoi
El algoritmo de Voronoi es una semi-verdad matemática, cuyo teorema fundamental está aún por confirmar y que está basado en el diagrama de Voronoi.
Imagina que tienes un mapa de una ciudad en donde haya una cantidad n de mastiles de teléfono. Un teléfono siempre conecta con los postes más cercanos, por lo que has de dividir la ciudad en zonas, en donde cada zona tenga exactamente la cobertura de uno de esos mástiles y se encuentre mas cerca del mastil de dicha zona que el de otra.
La resolución de éste particionado zonal de un territorio definido se dispersa mediante el diagrama de Voronoi, y se resuelve matemáticamente mediante una ecuación del tipo n log n para permutar varios algoritmos; por lo que también podría hacerse como un límite cuando la variable distancia(s) tienda a 0.
Además ésta pequeña característica de resolución de posicionamiento también podría resolverse mediante teoremas geométrico como son: La Triangulación Delaunay o la aplicación de Convex Hull.
Hay un programa (applet) en Java que desarrolla todas las posibilidades de éste diagrama mediante la ejecución de su algoritmo, en lo que se denomina “el algoritmo de la fortune” que son las posibles resoluciones que existen a Voronoi. Las opciones del programa son muy sencillas y podemos elegir que nosotros queramos.
Descarga | Fortune’s Algorithm
Julio 7th, 2008 a las 14:39
/* Disclaimer: siento ser tocapelotas pero es que este tema me toca muy de cerca y habéis dicho cosas que no me cuadran nada */
El diagrama de Voronoi es una cosa muy concreta y bien definida: dado un espacio métrico y una serie de puntos de ese espacio (llamémoslos sites), su diagrama de Voronoi es una partición del mismo en regiones disjuntas tales que, todo punto de una región tiene como site más cercano al mismo que el resto de puntos de esa región.
Técnicamente esto es particionar el espacio en clases de equivalencia según la relación “mi site más cercano es…”.
Existen muchos algoritmos que permiten calcular el diagrama de Voronoi en el plano real con la distancia euclídea. Los más eficientes lo hacen en tiempo n log n si bien hay algunos que también se usan y tardan n².
Cuando dices que el Teorema Fundamental no está aún demostrado supongo que te refieres al teorema que acota el tiempo mínimo necesario para calcular el diagrama de Voronoi en un espacio vectorial real de dimensión n. Aunque en vez de semi-verdad matemática yo hubiese usado hipótesis para referirme a ello.
Por otra parte, la Triangulación de Delanuay también es algo bien definido si bien es algo más difícil de explicar. En cualquier caso no es un teorema. En el mismo sentido, Convex Hull es, literalmente, la Envolvente Convexa que es, por definición, el politopo convexo más pequeño que contiene una serie de puntos (en el plano real sería el polígono convexo más pequeño).
Una vez calculado el diagrama de Voronoi de una serie de puntos es muy sencillo construir la Triangulación de Dalanuay y la Envolvente Convexa de los mismos (se hace en tiempo lineal). En el sentido contrario funciona con Delanuay (si tienes la triangulación de Delanuay puedes reconstruir el diagrama de Voronoi) pero no con la envolvente convexa (es más práctico empezar de cero que usar la envolvente convexa para reconstruir Voronoi).
Y finalmente, no entiendo qué quieres decir con:
Julio 21st, 2009 a las 17:19
hola
queria consultarle por algun software para windows que se puedan calcular los diagramas de voronoi en 3d (poliedros)
Saludos y gracias desde ya!