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!


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.

| cite | improve this answer | |
  • 4
    $\begingroup$ For those who don't know, MMP = Mitchell, Mount, Papamaditriou, "The Discrete Geodesic Problem," 1987. $\endgroup$ – Joseph O'Rourke Jan 15 '12 at 14:32
  • $\begingroup$ Thanks, Sariel! This seems correct, and explains why no one has written a separate paper on the topic. $\endgroup$ – Joseph O'Rourke Jan 15 '12 at 14:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.