کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
435860 | 689945 | 2015 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Nonconvex cases for carpenter's rulers
ترجمه فارسی عنوان
موارد غیر محکم برای حاکمان نجار
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
حاکم کارپنتر، مورد جهانی، الگوریتم تاشو
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
Journal: Theoretical Computer Science - Volume 586, 27 June 2015, Pages 12–25
نویسندگان
Ke Chen, Adrian Dumitrescu,