A simple algorithm for 2D Voronoi diagrams

In this video we will learn a simple algorithm for generating Voronoi diagrams. Given a set of points on the plane, the idea is to create, for each point, a polygon that encloses the region of the plane that is closest to that point.
Voronoi diagrams are a type of spatial partitioning diagram that divide a plane into regions based on the distance to a set of points. They are used in a variety of applications, including computer graphics, image processing, and machine learning.
By the end of this video, you will be able to understand and implement the Voronoi diagram algorithm in your own code.
Pseudocode (short version): gist.github.co...
Pseudocode (long version): gist.github.co...
JavaScript code: gist.github.co...
/ edgardocpu

[@aleksandrstukalov]

This is an awesome explanation of the algorithm! Thank you for sharing such a helpful content!❤❤❤

[@shihyuehjan3835]

Thank you so much for the video!

[@unveil7762]

This is very cool thank you

[@starplatinum3305]

Amazing

[@tedlorance6968]

Out of curiosity, is there a known or best-guess optimal or near-optimal value for the padding in the algorithm? Perhaps related to the mean distance between the sites?

[@gutzimmumdo4910]

what's the time complexity of this algo?

[@uncleole503]

this is very different from Fortune's algorithm

[@aleksandrstukalov]

Is there any research paper that you took this algorithm from?

[@EdgarProgrammator]

No, I couldn't find an easy, step-by-step algorithm for building Voronoi diagrams (unlike Delaunay triangulation algorithms, which are easy to find). That's why I created this video.

[@Kewargs]

​@@EdgarProgrammatorWhat about the Fortune sweep algorithm?

[@jcaceres149]

However, this algorithm is not optimal in the worst case, and it does not deal with unbounded Voronoi cells