Paper by Erik D. Demaine
- Daniel Kane, Gregory N. Price, and Erik D. Demaine, “A pseudopolynomial algorithm for Alexandrov's Theorem”, in Proceedings of the 11th Algorithms and Data Structures Symposium (WADS 2009), Lecture Notes in Computer Science, volume 5664, Banff, Alberta, Canada, August 21–23, 2009, pages 435–446.
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.
- This paper is also available from SpringerLink.
- Copyright held by the authors.
- The paper is 12 pages.
- The paper is available in PostScript (342k), gzipped PostScript (163k), and PDF (197k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated January 8, 2018 by