Metric Combinatorics of Convex Polyhedra: Cut Loci and Nonoverlapping Unfoldings
Metric Combinatorics of Convex Polyhedra: Cut Loci and Nonoverlapping Unfoldings
复制标题
凸多面体的度量组合：切割轨迹和非重叠展开
DOI：
--
复制
发表时间：
2003
影响因子：
0.8
通讯作者：
I. Pak
中科院分区：
文献类型：
--
作者：
Ezra Miller;I. Pak
设S是d+1维凸多面体的边界，或更一般地，设S是凸多面体伪流形。我们证明了S有一个多面体非重叠开折成
${Bbb{R}}^{d}$
，所以度量空间S是从一个封闭的（通常是非凸的）多面体球中得到的，
${Bbb{R}}^{d}$
通过等距地识别成对的边界面。我们的存在性证明利用了远离源点v∈S的测地线流，这是从v处的切空间到S的指数映射。我们的特点切割轨迹（封闭的一组点在S中有一个以上的最短路径v）作为一个多面体复杂的Voronoi图方面的小平面。分析波前的无穷小展开，该波前由S上与v保持恒定距离的点组成，产生了一种算法方法，用于在每个小平面上构造Voronoi图，从而展开S。该算法，我们提供了伪代码，解决了离散测地线问题。它的主要结构是将三多面体边界的源展开推广为
${Bbb{R}}^{2}$
.本文给出了凸多面体边界上最短路的个数和凸多面体的连续开折的一些结果。我们还评论了非凸流形的内在非多项式复杂性。
AbstractLet S be the boundary of a convex polytope of dimension d+1, or more generally let S be a convex polyhedral pseudomanifold. We prove that S has a polyhedral nonoverlapping unfolding into
${Bbb{R}}^{d}$
, so the metric space S is obtained from a closed (usually nonconvex) polyhedral ball in
${Bbb{R}}^{d}$
by identifying pairs of boundary faces isometrically. Our existence proof exploits geodesic flow away from a source point v∈S, which is the exponential map to S from the tangent space at v. We characterize the cut locus (the closure of the set of points in S with more than one shortest path to v) as a polyhedral complex in terms of Voronoi diagrams on facets. Analyzing infinitesimal expansion of the wavefront consisting of points at constant distance from v on S produces an algorithmic method for constructing Voronoi diagrams in each facet, and hence the unfolding of S. The algorithm, for which we provide pseudocode, solves the discrete geodesic problem. Its main construction generalizes the source unfolding for boundaries of three-polytopes into
${Bbb{R}}^{2}$
. We present conjectures concerning the number of shortest paths on the boundaries of convex polyhedra, and concerning continuous unfolding of convex polyhedra. We also comment on the intrinsic nonpolynomial complexity of nonconvex manifolds.