Nonoverlap of the star unfolding
Nonoverlap of the star unfolding
复制标题
恒星展开的非重叠
DOI：
10.1145/109648.109660
复制
发表时间：
1991
影响因子：
0.8
通讯作者：
J. O'Rourke
中科院分区：
文献类型：
--
作者：
B. Aronov;J. O'Rourke
凸多面体关于其表面上的点x的星形展开是通过沿着从x到每个顶点的最短路径切割曲面，并在平面上展平曲面而得到的。我们建立了星展开的两个主要性质：1.它不自重叠：它是一个简单的多边形.2.展开中的脊树，它是从x有一条以上最短路径的点的轨迹，精确地说是X的像的Voronoi图，仅限于展开.
这两个性质允许在概念上简化与多面体上的最短路径有关的几个算法，并且有时还可以改善最坏情况的复杂性：·可以通过特别简单的O(N2)算法来实现脊树的构造(例如，为了准备最短路径查询)。这不是最坏情况下的复杂性改进，但却是一个相当大的简化。·多面体上所有最短路径“边序列”的确切集合可以用一种比以前已知的算法简单得多的算法找到，其时间改进大约是旧的界限Ofo(N7logn)的n倍。·多边形的测地线直径可以在o(N9logn)时间内找到，这是对以前BESTO(N10)算法的改进。
我们的结果提出了关于一般凸面“展开”的猜想。
AbstractThe star unfolding of a convex polytope with respect to a pointx on its surface is obtained by cutting the surface along the shortest paths fromx to every vertex, and flattening the surface on the plane. We establish two main properties of the star unfolding:1.It does not self-overlap: it is a simple polygon.2.The ridge tree in the unfolding, which is the locus of points with more than one shortest path fromx, is precisely the Voronoi diagram of the images ofx, restricted to the unfolding.
These two properties permit conceptual simplification of several algorithms concerned with shortest paths on polytopes, and sometimes a worst-case complexity improvement as well:•The construction of the ridge tree (in preparation for shortest-path queries, for instance) can be achieved by an especially simpleO(n2) algorithm. This is no worst-case complexity improvement, but a considerable simplification nonetheless.•The exact set of all shortest-path “edge sequences” on a polytope can be found by an algorithm considerably simpler than was known previously, with a time improvement of roughly a factor ofn over the old bound ofO(n7 logn).•The geodesic diameter of a polygon can be found inO(n9 logn) time, an improvement of the previous bestO(n10) algorithm.
Our results suggest conjectures on “unfoldings” of general convex surfaces.