There are about 2e5 input points and 6e5 output edges, and generation takes about 35 seconds on a 1.2GHz Marvell Feroceon 88FR131 (a QNAP TS-119) using g++ version 4.4.2 -O3.
I am wondering if this also includes image generation time. On my nettop with an Intel Celeron U3400 1.07 GHz, g++ 4.4.1 it takes around 3-4 seconds and on my PC with i5-7600 2.8 GHz, g++ 4.6.1 just 0.6 seconds. It needs to be quite a lot faster than that, but it's not a bad start :-) Actually it's already very fast. By performance, construction of Voronoi diagram of 2e5 input points is equivalent to insertion of 2e6 pair<int, int> into std::set. So I guess your result of 35 seconds is very architecture specific or hides some details. My main performance concern is the overhead of doing O(log N) lookup to get
from the output vertices back to the corresponding input points.
As I mentioned I could expose index of the site event within the initial input set, thus this will require O(1) time. I will also need to investigate how much RAM is needed. This is already available in benchmarks. The memory usage of the current Voronoi diagram data structure for the set of 1e5 input points is 23 megabytes. Thanks, Andrii