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!


1 Answer 1


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.

  • 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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