| A Pseudopolynomial Algorithm for Alexandrov's Theorem (2009) | |||||||||||||
Abstract | |||||||||||||
| 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 given the metric, and prove a pseudopolynomial bound on its running time.. @InProceedings{kane_et_al:DSP:2009:2032, author = {Daniel Kane and Gregory Nathan Price and Erik Demaine}, title = {A Pseudopolynomial Algorithm for Alexandrov's Theorem}, booktitle = {Computational Geometry}, year = {2009}, editor = {Pankaj Kumar Agarwal and Helmut Alt and Monique Teillaud}, number = {09111}, series = {Dagstuhl Seminar Proceedings}, ISSN = {1862-4405}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany}, address = {Dagstuhl, Germany}, URL = {http://drops.dagstuhl.de/opus/volltexte/2009/2032}, annote = {Keywords: Folding, metrics, pseudopolynomial, algorithms} } | |||||||||||||
Publication details | |||||||||||||
| |||||||||||||