## Sneak preview: carpenter's ruler problems

5. Sneak preview: carpenter's ruler problems

The renewed interested in linkages that occurred in recent years has grown out of the availability of new ideas and tools that evolve from the interest of the mathematics and computer science communities in problems involving geometry and the complexity of geometric problems. In particular, problems have been posed about the computational complexity of motion planning problems for robots (i.e. what is the complexity of the best algorithm for getting a robot to move between two positions in the presence of obstacles).

A carpenter's ruler is a collection of links (i.e. a path) of various lengths confined to a plane. What can be said about such a simple device? Two rather surprising problems which have had dramatic implications will be described.

The first is the question of, given a carpenter's ruler, what is the complexity of finding the smallest case into which it will fit. Of course we are talking about a case where the height of the case is zero! More specifically, if the ruler consists of links of length l1, ..., ln (where the link lengths can be either different or the same) by folding the ruler at its joints, what is the smallest interval which it can be folded into? For example, if the links in order are of length 1, 3, 2, 4 in its unfolded position the ruler is length 10 but it can be enclosed in a box of length 5. Different orderings of the links can have different minimal boxes which will contain the ruler. For example, if the ruler has links of length 8, 7, and 5 in this order, the ruler can be folded into a box on length 8, but if the links occur in the order 8, 5, and 7, then the smallest box they can be folded into is a box of length 10! We are interested in the complexity of algorithms to find the smallest case.

Another problem about carpenter's rulers has a very different flavor. Imagine that one has a carpenter's ruler bent in a very complicated way. The diagram below shows an example. Is it possible to straighten this ruler into segments which lie along a straight line using motions which never allow sections of the ruler to interpenetrate?

Details about these two problems will be discussed in a future column following up this one. Answers to both of the problems are now known. The first was answered by John Hopcroft (Cornell), Deborah Joseph (Wisconsin), and Sue Whitesides (McGill). The second was answered by Robert Connelly (Cornell), Erik Demaine (MIT), and Günther Röte (Berlin) with additional exciting insights provided by Ileana Steinu (Smith).