Podemos verificar que cada uma das células de Voronoi pode ser criada a partir da interseção dos semiplanos cuja linha limítrofe equidista dois sítios do diagrama.
Um dado sítio V(pi) é formado pela interseção dos semiplanos h(pi,pj) para j=1,...,n (j diferente de i), onde h(pi,pj) é o semiplano que contém pi e cuja reta que o limita é equidistante a pi e pj.
Um algotítmo como este que calcule o diagrama de Voronoi utilizando a inteseção de semiplanos levará um tempo da ordem de O(n logn) por célula de Voronoi, o que acarretará um tempo total da ordem de O(n2log n).
Em 1985, Fortune desenvolveu um algorítmo por varredura muito elegante e simples de complexidade de tempo O(n log n).
http://www.diku.dk/students/duff/Fortune/