A Pseudopolynomial Algorithm for Alexandrov's Theorem
A Pseudopolynomial Algorithm for Alexandrov's Theorem
复制标题
亚历山德罗夫定理的伪多项式算法
DOI：
10.1007/978-3-642-03367-4_38
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
E. Demaine
中科院分区：
文献类型：
--
作者：
D. Kane;Gregory N. Price;E. Demaine
Alexandrov定理指出，每个具有凸多面体所需的全局拓扑和局部几何的度量实际上都是某个凸多面体的内蕴度量。Bobenko和Izmstiev最近的工作描述了一个微分方程，它的解是对应于给定度量的多面体。在此基础上，给出了一种计算任意精度的多面体的算法，并证明了其运行时间的一个伪多项式界。
Alexandrov’s Theorem states that every metric with the global topology and local geometry required of a convex polyhedron is in fact the intrinsic metric of some convex polyhedron. Recent work by Bobenko and Izmestiev describes a differential equation whose solution is the polyhedron corresponding to a given metric. We describe an algorithm based on this differential equation to compute the polyhedron to arbitrary precision given the metric, and prove a pseudopolynomial bound on its running time.