کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10225738 1701207 2018 18 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Bumpy pyramid folding
ترجمه فارسی عنوان
تاشو هرم پرپیچ و خم
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We investigate folding problems for a class of petal (or star-like) polygons P, which have an n-polygonal base B surrounded by a sequence of triangles for which adjacent pairs of sides have equal length. We give linear time algorithms using constant precision to determine if P can fold to a pyramid with flat base B, and to determine a triangulation of B (crease pattern) that allows folding into a convex (triangulated) polyhedron. By Alexandrov's Theorem, the crease pattern is unique if it exists, but the general algorithm known for this theorem is pseudo-polynomial, with running time O(n456.5); ours is the first efficient algorithm for Alexandrov's Theorem for a special class of polyhedra. We also give a polynomial time algorithm that finds the crease pattern to produce the maximum volume triangulated polyhedron.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 75, December 2018, Pages 22-31
نویسندگان
, , , , , ,