The Number of Shortest Paths on the Surface of a Polyhedron
David M. Mount · SIAM Journal on Computing · 1990
It is proven that if the shortest paths on the surface of a convex polyhedron are grouped into equivalence classes according to the sequences of edges that they cross, then the resulting number of equivalence classes is $O(n^{4})$, where n is the number of vertices of the polyhedron. In fact, the more general result that any family of pseudosegments (a set of open simple curves on the plane such that two curves intersect each other in at most one point) lying on a planar subdivision defined by n other pseudosegments can give rise to at most $O(n^{4})$ edge sequences is also proven. This bound is shown to be asymptotically tight, by giving an example of a family of polyhedra with $\Omega (n^{4})$ shortest path equivalence classes.