<p>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. </p>

<p>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.</p>

CC BY-SA 3.0
2012-01-15T14:32:30.200Z
For those who don't know, MMP = Mitchell, Mount, Papamaditriou, "[The Discrete Geodesic Problem](http://dl.acm.org/citation.cfm?id=33372)," 1987.
Joseph O'Rourke
CC BY-SA 3.0
2012-01-15T14:33:31.163Z
Thanks, Sariel! This seems correct, and explains why no one has written a separate paper on the topic.
Joseph O'Rourke
CC BY-SA 3.0
2012-01-15T06:05:07.283Z
2012-01-15T06:05:07.283Z
Sariel Har-Peled
<p>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!</p>

<reference-request><cg.comp-geom>
Voronoi diagram on surface of polyhedron
Joseph O'Rourke
# Voronoi diagram on surface of polyhedron

(Asked by: username_0 on 2012-01-14)

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!

**Tags:** reference-request, cg.comp-geom

---

## 1 answers

### Answer by username_1 on 2012-01-15. Score: 6 | Accepted answer

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.

> **Comments:**
> **username_0**: For those who don't know, MMP = Mitchell, Mount, Papamaditriou, "[The Discrete Geodesic Problem](http://dl.acm.org/citation.cfm?id=33372)," 1987.  
> **username_0**: Thanks, Sariel! This seems correct, and explains why no one has written a separate paper on the topic.  

---

