Does anyone know of work on computing the Voronoi diagram of a set of points on a polyhedron, where distance is measured by shortest paths on the surface? I am particularly interested in convex polyhedra. I have a vague memory that this has been explored, but my memory is too vague to locate any papers. Thanks for pointers!
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
You can just use MMP k times, if you have k sites. For every face, you have to compute the additive weighted Voronoi diagram, and the overlay of k such diagrams still have linear complexity (because, it is just a planar additive weighted Voronoi idagram). As such, for a polytope with n faces and k sites, this takes $O(n^2 k \log n)$ time. You can use the latest monstrorisity by Sharir and Schriber and do it in $O(nk log n)$ time - but is not clear how to overlay the diagrams on every face. It is probably a good idea to look at their paper and see if they do something for this case.
As far as approximation, it is not hard to show that one can build a space decomposition of complexity $O(k/\epsilon^{O(1)} )$ such that given a query point, one can report the approximate nearest-neighbor on the polytope in $O( \log (k/\epsilon) )$ time. I think using some newer machinery, one can in fact also return the approximate distance in this time.
answered Jan 15, 2012 at 6:05
-
4$\begingroup$ For those who don't know, MMP = Mitchell, Mount, Papamaditriou, "The Discrete Geodesic Problem," 1987. $\endgroup$ Commented Jan 15, 2012 at 14:32
-
$\begingroup$ Thanks, Sariel! This seems correct, and explains why no one has written a separate paper on the topic. $\endgroup$ Commented Jan 15, 2012 at 14:33