A Pseudopolynomial Algorithm for Alexandrov's Theorem

A Pseudopolynomial Algorithm for Alexandrov's Theorem

27 May 2009 | Daniel Kane, Gregory N. Price, and Erik D. Demaine
This paper presents a pseudopolynomial-time algorithm for Alexandrov's Theorem, which states that every metric with the global topology and local geometry required of a convex polyhedron is the intrinsic metric of some convex polyhedron. The algorithm is based on a differential equation introduced by Bobenko and Izmestiev, which allows the computation of a convex polyhedron corresponding to a given metric. The algorithm's running time is bounded by a pseudopolynomial function of the number of vertices, the ratio of the largest to smallest distance between vertices, and the defect (discrete Gaussian curvature) at each vertex. The algorithm computes an embedding of the metric that is accurate to within a small epsilon and convex to within a small epsilon. The algorithm works by iteratively adjusting the radii of the vertices of the polyhedron until the resulting embedding satisfies the desired accuracy and convexity conditions. The algorithm's performance is analyzed using bounds on geometric quantities such as the Jacobian and Hessian, which are shown to be pseudopolynomially bounded. The algorithm is proven to produce an accurate and convex embedding of the metric in pseudopolynomial time.This paper presents a pseudopolynomial-time algorithm for Alexandrov's Theorem, which states that every metric with the global topology and local geometry required of a convex polyhedron is the intrinsic metric of some convex polyhedron. The algorithm is based on a differential equation introduced by Bobenko and Izmestiev, which allows the computation of a convex polyhedron corresponding to a given metric. The algorithm's running time is bounded by a pseudopolynomial function of the number of vertices, the ratio of the largest to smallest distance between vertices, and the defect (discrete Gaussian curvature) at each vertex. The algorithm computes an embedding of the metric that is accurate to within a small epsilon and convex to within a small epsilon. The algorithm works by iteratively adjusting the radii of the vertices of the polyhedron until the resulting embedding satisfies the desired accuracy and convexity conditions. The algorithm's performance is analyzed using bounds on geometric quantities such as the Jacobian and Hessian, which are shown to be pseudopolynomially bounded. The algorithm is proven to produce an accurate and convex embedding of the metric in pseudopolynomial time.
Reach us at info@study.space