On Thursday, 15 May 2014 09:36:06 UTC+2, Ariel Keselman wrote: > > they are MIT licensed, no need for permission :) > > how efficient is Voroni construction using conic hulls, I think Qhull > which uses convex hulls is way slower than what I plan with the algorithms > described in here: http://arxiv.org/pdf/0901.4107v3.pdf >
Looking at the paper more carefully, I see that you only need to do insertion of generators and not removal. I believe that the incremental insertion method that I have implemented is similar but has the chance to be somewhat more efficient. It falls out pretty naturally from thinking about convex/conic hulls. Both methods insert one generator at a time. The method in the paper does this by first splitting the facet that contains the generator, and then flipping neighbouring pairs of facets until Delaunayhood is restored. The method that I have implemented first finds one facet in the hull that is dominated by the generator (that the generator is in front of). This might be the facet that contains the generator as seen in the Delaunay triangulation, or it might be one of the other facets that will be replaced. It then finds the whole cluster of dominated facets, which is connected. It finally removes the dominated facets and then forms the new facets by extruding the edges between removed and unremoved facets to the newly inserted generator. The potential efficiency increase comes from two places: - Fewer predicates to test. We only need to test once for each facet whether it is dominated (in-circle test). No additional predicates to test if an edge is flippable, and if so in which way. - No intermediate facets are created when inserting a generator. The thing that becomes slightly more complex is reconnecting the new facets with their neighbours, but that only means walking through a few facets to find the right connection. The end result is of course the same after a generator has been inserted. Now I'm not saying that my current implementation is very efficient :) But I think that the method might be of interest to you.
