On Thursday, 15 May 2014 09:36:06 UTC+2, Ariel Keselman wrote: > > they are MIT licensed, no need for permission :) >
Right, I missed that. Good :) > 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 > Short answer: I don't think that it should have to be different. Long anwser: The way that I see it, the difference is more about how you think about what you are doing than the actual implementation. I find that working with conic hulls unifies some concepts compared to Delaunay triangulations/Voronoi diagrams/power diagrams. (But they can be specialized again for efficiency.) The data structures and predicates are really the same. Perhaps the fact that Delaunay triangulations correspond to a special case of convex hulls (where all the points lie on a paraboloid surface) might allow some simplified algorithms compared to the general case, but those could still be implemented in the same framework. Looking at the paper, the data structures are almost identical to what I use. A Delaunay triangulation in R^n corresponds to a conic hull in R^(n+2). I describe the mesh by the collection of facets of the conic hull; each facet is made up of n+1 generators and corresponds exactly to a simplex in the triangulation. For each facet i store the generators, keeping track of their positive orientation, and the neighboring facet opposite to each generator. The Delaunay triangulation of a set of generators x_k in R^n can be found by taking the conic hull of the generators y_k, y_k = [1, x_k, ||x_k||^2] (whether we represent the generators as vectors in R^(n+2) or just store x_k is of course up to us.) We actually only need the lower hull. One way to avoid constructing the upper hull is to add the generator y_0 = [0, zeros(n), 1] which I will call the *primary generator*. Note that it lies outside the paraboloid surface; since the conic hull is pretty much a conic hull in homogeneous coordinates it can be seen the infinity point that generators go to when ||x|| goes to infinity. By including the primary generator we get a complete conic hull without having to represent the upper hull (which would correspond to the furthest point Voronoi diagram). This makes it possible to insert generators outside the convex hull of the existing x_k without adding any special cases. For conic hulls in R^(n+2), we only need one predicate: the sign of the determinant of n+2 generators (concatenated in some given order into a matrix). This can be seen as forming the linear function which is zero in the plane of the n+1 first generators, and evaluating it in the last one. The plane function can be evaluated with a partial determinant computation and could be stored with e.g. each facet. It gives homogeneous coordinates for the corresponding Voronoi/power diagram vertex. With all generators on the paraboloid, the determinant predicate is equivalent to the determinant (3) in the paper (the in-circle test). With the primary generator as one of the generators, it reduces to the orientation test (4) in the paper. (Up to the sign of the permutation needed to bring out the primary generator to a fixed index in the list.) So the predicates are really the same. If one doesn't want to have the primary generator in the hull, one could work with an incomplete hull where the links to the facets that would contain it are undefined. One would then have to make sure that the implicit facets would always remain as facets of the hull, analogous to not inserting generators into the Delaunay triangulation outside of the convex hull of the current ones. I really liked the overview of different algorithms for Delaunay triangulations in the paper; I didn't know that the flipping method has such good perfomance in practice. I have considered it but haven't worked out yet how to make it foolproof in the case of generators in degenerate position, so I started with a method that I could. The method applied to a lower convex hull would mean to try to flip simplexes formed by adjacent facets if it increases the volume of the hull, and all new facets are still oriented downward. So I think that what we want to achieve is actually very similar. I'm not interested in conic hulls for their own sake but for constructing Voronoi/power diagrams, and also in the specializations that apply to these cases. Now if/when I will get the time to go ahead and do all this stuff is another matter unfortunately...
