کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
435860 689945 2015 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Nonconvex cases for carpenter's rulers
ترجمه فارسی عنوان
موارد غیر محکم برای حاکمان نجار
کلمات کلیدی
حاکم کارپنتر، مورد جهانی، الگوریتم تاشو
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

We consider the carpenter's ruler folding problem in the plane, i.e., finding a minimum area shape with diameter 1 that accommodates foldings of any ruler whose longest link has length 1. An upper bound of π/3−3/4=0.614… and a lower bound of 10+25/8=0.475… are known for convex cases. We generalize the problem to simple nonconvex cases: in this setting we improve the upper bound to 0.583 and establish the first lower bound of 0.073. A variation is to consider rulers with at most k   links. The current best convex upper bounds are (about) 0.486 for k=3,4k=3,4 and π/6=0.523…π/6=0.523… for k=5,6k=5,6. These bounds also apply to nonconvex cases. We derive a better nonconvex upper bound of 0.296 for k=3,4k=3,4.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 586, 27 June 2015, Pages 12–25
نویسندگان
, ,