Paper by Erik D. Demaine

Reference:

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.

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 to arbitrary precision given the metric, and prove a pseudopolynomial bound on its running time.

Comments:

This paper is also available from SpringerLink.

Copyright:

Copyright held by the authors.

Length:

The paper is 12 pages.

Availability:

The paper is available in PostScript (342k), gzipped PostScript (163k), and PDF (197k).

See information on file formats.

[Google Scholar search]