<div dir="ltr">Hi Nathan,<br><div><div class="gmail_extra"><br><div class="gmail_quote">2018-06-07 16:15 GMT+01:00 Nathan Einstein <span dir="ltr"><<a href="mailto:njeinstein@gmail.com" target="_blank">njeinstein@gmail.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hi all,<br><br><div>I’d like to create Voronoi polygons for a set of about 11 million points. ST_VoronoiPolygons works fine for a subset of ~3 million of these points, though the function’s processing speed seems to scale non-linearly in the number of points. I therefore haven’t been able to get it to work for the entire dataset, even when left running overnight (but notably, ArcGIS completes it in under an hour). <br><br></div><div>Unfortunately, it doesn’t seem like there’s any simple “divide-and-conquer”-type solution; because the Voronoi polygons on the edges will be irregularly shaped, I haven’t been able to come up with a clean way to combine the results from subsets of the full dataset.<br></div><div><br></div><div>Does anyone have any suggestions? <br></div></div></blockquote><div><br></div><div>As you said, there is not a trivial way to make work Voronoi polygons creation in subsets of data, for then being put together. You can do this just in case you can accept irregularities at the edges of each subset. Though it is normal that processing speed doesn't scale linearly (the complexity of the algorithm should be ~O(N logN) in the best case), it is strange that ArcGIS performs with a so large difference, being based both ArcGIS and ST_VoronoiPolygons functions on triangulation. Could check if both processing are performed with the same tollerance (i.e. the distance below which two points are considered as one)? In really dense datasets different tollerance could bring to different starting points in input to the algorithm.<br><br></div><div>Anyway, I'd be happy to know more from anyone has a good answer to this question.<br><br></div><div>All the best,<br></div><div>Giuseppe.<br></div></div></div></div></div>