CGAL users discussion list

[Phillip Keldenich <>]

Hello everyone,

do you know of any implementation (within CGAL, done using CGAL, or even
unrelated) of algorithms for computing Higher-Order Voronoi Diagrams or
Higher-Order Delaunay Graphs?

In particular, I am interested in the case of order 17 which comes up for
bottleneck matchings; the order is thus constant, but way too large to make
simple O(n^k) algorithms such as the one used by the k-order Voronoi Diagram
IPElet feasible.
There are O(knlog n) algorithms, but I could not find any implementation
and/or practical evaluation of these; engineering them properly, including
handling of degeneracies, seems to be non-straightforward.

I would be glad if anyone could provide me with a helpful pointer.

Cheers & Merry Christmas,
Phillip



--
Sent from: http://cgal-discuss.949826.n4.nabble.com/