A pseudopolynomial algorithm for Alexandrov's theorem
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 t...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer
2011
|
| Online Access: | http://hdl.handle.net/1721.1/61985 https://orcid.org/0000-0003-3803-5703 |
| _version_ | 1826213693547872256 |
|---|---|
| author | Kane, Daniel Price, Gregory N. Demaine, Erik D. |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Kane, Daniel Price, Gregory N. Demaine, Erik D. |
| author_sort | Kane, Daniel |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T15:53:19Z |
| format | Article |
| id | mit-1721.1/61985 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:53:19Z |
| publishDate | 2011 |
| publisher | Springer |
| record_format | dspace |
| spelling | mit-1721.1/619852022-09-29T16:48:08Z A pseudopolynomial algorithm for Alexandrov's theorem Kane, Daniel Price, Gregory N. Demaine, Erik D. Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D. Price, Gregory N. Demaine, Erik D. 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. National Science Foundation (U.S.) (Career award CCF-0347776) National Science Foundation (U.S.). Graduate Research Fellowship Program 2011-03-28T20:29:25Z 2011-03-28T20:29:25Z 2009-01 Article http://purl.org/eprint/type/ConferencePaper 978-3-642-03367-4 http://hdl.handle.net/1721.1/61985 Kane, Daniel, Gregory N. Price and Erik D. Demaine, "A Pseudopolynomial Algorithm for Alexandrov’s Theorem" Algorithms and data structures (Lecture notes in computer science, v. 5664,2009)435-446. Copyright © 2009, Springer . https://orcid.org/0000-0003-3803-5703 en_US http://dx.doi.org/10.1007/978-3-642-03367-4_38 Algorithms and data structures (Conference) Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Springer MIT web domain |
| spellingShingle | Kane, Daniel Price, Gregory N. Demaine, Erik D. A pseudopolynomial algorithm for Alexandrov's theorem |
| title | A pseudopolynomial algorithm for Alexandrov's theorem |
| title_full | A pseudopolynomial algorithm for Alexandrov's theorem |
| title_fullStr | A pseudopolynomial algorithm for Alexandrov's theorem |
| title_full_unstemmed | A pseudopolynomial algorithm for Alexandrov's theorem |
| title_short | A pseudopolynomial algorithm for Alexandrov's theorem |
| title_sort | pseudopolynomial algorithm for alexandrov s theorem |
| url | http://hdl.handle.net/1721.1/61985 https://orcid.org/0000-0003-3803-5703 |
| work_keys_str_mv | AT kanedaniel apseudopolynomialalgorithmforalexandrovstheorem AT pricegregoryn apseudopolynomialalgorithmforalexandrovstheorem AT demaineerikd apseudopolynomialalgorithmforalexandrovstheorem AT kanedaniel pseudopolynomialalgorithmforalexandrovstheorem AT pricegregoryn pseudopolynomialalgorithmforalexandrovstheorem AT demaineerikd pseudopolynomialalgorithmforalexandrovstheorem |