27 May 2009 | Daniel Kane*, Gregory N. Price†‡, and Erik D. Demaine‡
This paper presents a pseudopolynomial algorithm to compute the embedding of a given polyhedral metric into \(\mathbb{R}^3\). The algorithm is based on a differential equation described by Bobenko and Izmestiev, which provides a solution that can be used to construct the embedding. The main theorem states that given a polyhedral metric with \(n\) vertices, a ratio \(S\) between the diameter and the smallest distance between vertices, and defect values \(\varepsilon_1\) and \(2\pi - \varepsilon_8\) at each vertex, an \(\varepsilon_6\)-accurate and \(\varepsilon_9\)-convex embedding can be found in time \(O(n^{913/2} S^{831} / (\varepsilon^{121} \varepsilon_1^{445} \varepsilon_8^{616}))\). The algorithm involves iteratively adjusting a radius assignment to minimize the curvature and ensuring the resulting generalized convex polyhedron fits nearly isometrically in \(\mathbb{R}^3\). The Jacobian and Hessian of the curvature function are pseudopolynomially bounded, ensuring the algorithm's efficiency. The proof of the main theorem and the bounds on the Jacobian and Hessian are detailed, providing a rigorous foundation for the algorithm's correctness and performance.This paper presents a pseudopolynomial algorithm to compute the embedding of a given polyhedral metric into \(\mathbb{R}^3\). The algorithm is based on a differential equation described by Bobenko and Izmestiev, which provides a solution that can be used to construct the embedding. The main theorem states that given a polyhedral metric with \(n\) vertices, a ratio \(S\) between the diameter and the smallest distance between vertices, and defect values \(\varepsilon_1\) and \(2\pi - \varepsilon_8\) at each vertex, an \(\varepsilon_6\)-accurate and \(\varepsilon_9\)-convex embedding can be found in time \(O(n^{913/2} S^{831} / (\varepsilon^{121} \varepsilon_1^{445} \varepsilon_8^{616}))\). The algorithm involves iteratively adjusting a radius assignment to minimize the curvature and ensuring the resulting generalized convex polyhedron fits nearly isometrically in \(\mathbb{R}^3\). The Jacobian and Hessian of the curvature function are pseudopolynomially bounded, ensuring the algorithm's efficiency. The proof of the main theorem and the bounds on the Jacobian and Hessian are detailed, providing a rigorous foundation for the algorithm's correctness and performance.