3 ms·
Voronoi tessellation in linear time
- RiderOfGiraffes 17y agoFrom the guidelines: > Please submit the original source. If a blog post > reports on something they found on another site, > submit the latter. Here's the actual item, rather than the reddit submission: http://asserttrue.blogspot.com/2010/02/voronoi-tessellation-in-linear-time.html http://asserttrue.blogspot.com/2010/02/voronoi-tessellation-...
- gjm11 17y agoThis algorithm works on a bitmap image. It takes time proportional to the number of pixels in the image, not the number of points 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. Apart from that, yeah, Voronoi diagram in linear time. (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 one-dimensional Voronoi diagrams are as difficult as sorting.)