diagrama de voronoi n-dimensional

Question

Hola, necesito calcular el diagrama de voronoi de un conjunto de puntos en$R^n$. No tengo mucha educación en el tema, ¿podría alguien señalarme las referencias correctas para que pueda

a) comprender la teoría detrás de ella;

b) implementar un algoritmo real para calcularlo.

PD Al buscar en Google, descubrí que necesito saber sobre gráficos euclidianos, pero no pude encontrar ninguna introducción decente. ¡Se agradecen los consejos!

Answer 1

Creo que el "levantamiento de los puntos en dimensiones$d+1$" a que se hace referencia en la respuesta de Joseph O'Rourke significa algo como esto:$(x_1,\dots,x_d) \mapsto (x_1,\dots,x_d,x_1^2+\cdots+x_d^2)$. Luego, los bordes del casco convexo de esos puntos en el espacio$d+1$ conectan las imágenes de los puntos que están conectados en la triangulación de Delaunay.