Easiest algorithm of Voronoi diagram to implement? [closed]

An easy algorithm to compute the Delaunay triangulation of a point set is flipping edges. Since a Delaunay triangulation is the dual graph of a Voronoi diagram, you can construct the diagram from the triangulation in linear time.

Unfortunately, the worst case running time of the flipping approach is O(n^2). Better algorithms such as Fortune’s line sweep exist, which take O(n log n) time. This is somewhat tricky to implement though. If you’re lazy (as I am), I would suggest looking for an existing implementation of a Delaunay triangulation, use it, and then compute the dual graph.

In general, a good book on the topic is Computational Geometry by de Berg et al.

Leave a Comment