A Pseudopolynomial Algorithm for Alexandrov's Theorem

Authors Daniel Kane, Gregory Nathan Price, Erik Demaine



PDF
Thumbnail PDF

File

DagSemProc.09111.2.pdf
  • Filesize: 239 kB
  • 22 pages

Document Identifiers

Author Details

Daniel Kane
Gregory Nathan Price
Erik Demaine

Cite AsGet BibTex

Daniel Kane, Gregory Nathan Price, and Erik Demaine. A Pseudopolynomial Algorithm for Alexandrov's Theorem. In Computational Geometry. Dagstuhl Seminar Proceedings, Volume 9111, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
https://doi.org/10.4230/DagSemProc.09111.2

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.
Keywords
  • Folding
  • metrics
  • pseudopolynomial
  • algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail