This algorithm works on a bitmap image. It takes time proportional to the number of <i>pixels</i> in the image, not the number of <i>points</i> you're computing the Voronoi diagram of. And what it computes is a pixel-resolution approximation to the Voronoi diagram, not the V.d. itself. And it uses a non-standard metric (in which "circles" are actually diamonds bounded by lines x+y=const and x-y=const) so it's not even an approximation to the Voronoi diagram you were probably expecting.<p>Apart from that, yeah, Voronoi diagram in linear time.<p>(There is no such thing as an algorithm that computes Voronoi diagrams in time linear in the number of points, because if you can compute Voronoi diagrams in time O(n) then you can sort just as quickly... in an embarrassingly simple way. If you have a set of distinct numbers a_i, take your points to be (a_i,0). Compute the Voronoi diagram; it tells you which points are adjacent because they're the ones whose regions share an edge. So now find the leftmost point -- time O(n) -- and then find its successors by stepping over those edges. Note that this means that <i>one-dimensional</i> Voronoi diagrams are as difficult as sorting.)