Re: [boost] [Review Request] Inclusion of the Boost.Polygon Voronoi Library

Subject: Re: [boost] [Review Request] Inclusion of the Boost.Polygon Voronoi Library
From: Andrii Sydorchuk (sydorchuk.andriy_at_[hidden])
Date: 2012-04-14 06:54:19

>
> 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