Soy un ingeniero de software y me han pedido investigar una implementación de Voronoi en cuatro dimensiones. No estoy pidiendo "teh codez" pero sí estoy interesado en tutoriales accesibles sobre la descomposición de Voronoi y/o implementaciones en cualquier dimensión. ¡Cualquier ayuda aquí sería muy apreciada!
Respuestas
¿Demasiados anuncios?
La encuesta estándar es Aurenhammer y Klein. ¿Ya has echado un vistazo a eso?
[Este sería un comentario, pero aún no tengo suficiente reputación en este sitio]
Jay Bazuzi
Puntos
194
Aunque no hayas pedido 'los códigos' :), qvoronoi es una implementación bastante buena de diagramas de Voronoi para dimensiones bajas (es decir, 4). De hecho, calcula la triangulación de Delaunay, la cual a su vez es construida por un algoritmo de cálculo de envolvente convexa (qhull) en una dimensión superior.
El algoritmo de envolvente convexa en sí mismo es una combinación de "el algoritmo Quickhull 2D con el algoritmo beneath-beyond para n dimensiones [c.f., Preparata & Shamos '85]"
