# Is there a computationally reasonable algorithm for generating a set of polygons from a set of 2d points?

Is there a known/existing algorithm for taking a 2D canvas covered in arbitrarily/randomly distributed points and dividing it entirely into a set of non-overlapping polygons? An example of the kind of result I'm looking for:

• Is it important that the algorithm should start with the set of points or is it OK if it achieves the effect some other way? (I don't know the answer in either case, but there's no reason to limit the answer if the randomly generated set of points were just your start at a solution rather than an intrinsic part of the problem.) – David Richerby Aug 4 '15 at 21:41
• You don't say which point would generate the above diagram. DW's "Voronoi" answer is great, unless you meant that the shared vertices were the initially defined points. – Vynce Aug 4 '15 at 23:43

You might be looking for a Voronoi diagram. Given a set $S$ of points, it creates one cell per point, where the cell for point $p$ contains everything that is closer to $p$ than to any other point in $S$. There are algorithms to compute a Voronoi diagram in $O(n \lg n)$ time, where $n$ is the number of points in your set.