Date of Award
Master of Science
Christine Cheng, Guangwu Xu
Carpenter's Ruler, Folding Algorithm, Universal Case
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 0.614 and a lower bound of 0.476 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 0.486 for k = 3, 4 and 0.523 for k = 5, 6. These bounds also apply to nonconvex cases. We derive a better nonconvex upper bound of 0.296 for k = 3, 4.
Chen, Ke, "Nonconvex Cases for Carpenter's Rulers" (2014). Theses and Dissertations. 577.