Geometry Boost List: [ggl] Voronoi diagram code?

Subject: [ggl] Voronoi diagram code?
From: Anders Wallin (anders.e.e.wallin)
Date: 2011-09-05 06:05:05

There is a recent conference paper by Held et al where floating-point
algorithms are compared to exact arithmetic/predicates, which you may
find interesting:
http://2011.cccg.ca/PDFschedule/papers/paper77.pdf

It's quite clear how to interpret the runtime results (exact
arithmetic slows down the vroni algorithm by a factor of 50-70).
However it's less clear to me how to interpret the accuracy data.

If anyone builds a set of test-cases and makes these publicly
available it would be interesting to redo these benchmarks. My code is
similar to vroni, but handles only point-generators at the moment.

Anders

> Hi Anders,
> As mentioned Mateusz it's a part of the Boost.Polygon library (not included
> in the release yet).?All the implementation details are done,?however it
> requires some code refactoring and documentation to suit Boost libraries
> release requirements. At the moment the code is
> under?https://svn.boost.org/svn/boost/sandbox/SOC/2010/sweepline
> There are three approaches used to build Voronoi diagram of points and line
> segments: sweepline algorithm, divide and conquer and incremental
> algorithms.?We used sweepline algorithm because it doesn't have voronoi
> diagram reconstruction step, thus it has simpler and clearer site processing
> logic (especially for the voronoi of segments).
> If this would help you, the incremental algorithm is implemented in the CGAL
> library.