Article ID Journal Published Year Pages File Type
435860 Theoretical Computer Science 2015 14 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,