Date of Award

May 2014

Degree Type

Thesis

Degree Name

Master of Science

Department

Computer Science

First Advisor

Adrian Dumitrescu

Committee Members

Christine Cheng, Guangwu Xu

Keywords

Carpenter's Ruler, Folding Algorithm, Universal Case

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 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.

Download

Share

COinS