The Number of Shortest Paths on the Surface of a Polyhedron
The Number of Shortest Paths on the Surface of a Polyhedron
复制标题
多面体表面上的最短路径数
DOI：
10.1137/0219040
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
D. Mount
中科院分区：
文献类型：
--
作者：
D. Mount
证明了如果将凸多面体表面上的最短路径根据其所穿过的边的序列分组为等价类，则得到等价类的个数为$O(n^{4})$，其中n为多面体的顶点数。事实上，在由n个其他伪线段定义的平面细分上的任何伪线段族（平面上两条曲线最多相交于一点的一组开放简单曲线）可以产生最多$O(n^{4})$个边序列的更一般的结果也得到了证明。通过给出一个具有$\Omega (n^{4})$最短路径等价类的多面体族的例子，证明了这个界是渐近紧的。
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.