\documentclass[11pt]{article}
\usepackage{dimacsmodules}
\usepackage{graphics}  %%invoke this if graphics won't work otherwise
\usepackage{theorem, latexsym}
\input amssym.def

\setlength{\topmargin}{0in}     % top of paper to head (less one inch)
\setlength{\headheight}{0in}    % height of the head
\setlength{\headsep}{0in}       % head to the top of the body
\setlength{\textheight}{9.00in} % height of the body
\setlength{\oddsidemargin}{0mm} % left edge of paper to body (less one inch)
\setlength{\evensidemargin}{0mm} % ditto, even pages
\setlength{\textwidth}{6.5in}   % width of body
\setlength{\topskip}{0in}       % top of body to bottom of first line of text
%\setlength{\footheight}{0.25in} % height of footer
%\setlength{\footskip}{0.50in}   % bottom of text to bottom of foot

%--------------from the book style file----------------------

\newcommand{\bC}{{\bf C}}
%\textwidth 16.2cm
%\evensidemargin 2mm
%\oddsidemargin 2mm
\newcommand{\sk}{\medskip}
\newcommand{\bsk}{\bigskip}
%\special{papersize=8.5in,11in}
%\newtheorem{thm}{Theorem}[chapter]
\newtheorem{thm}{Theorem}[section]
\newtheorem{thrm}{Theorem}%[chapter]
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{coro}[thm]{Corollary}
\newtheorem{prop}[thm]{Proposition}

%\theoremstyle{definition}
\theorembodyfont{\rmfamily}
\newtheorem{defn}[thm]{Definition}
\newtheorem{examp}[thm]{Example}
\newtheorem{xca}[thrm]{Exercise}

%\theoremstyle{remark}
\newtheorem{rmk}[thm]{Remark}

%\numberwithin{section}{chapter}
%\numberwithin{equation}{chapter}
%%\numberwithin{thm}{section}
%\numberwithin{table}{section}
%%\numberwithin{figure}{section}

%\renewcommand{\include}{\input}

\parindent2em
\newcommand{\nsk}{\addvspace{-5ex}}
\newcommand{\bt}{\begin{thm}}
\newcommand{\et}{\end{thm}}
\newcommand{\bl}{\begin{lemma}}
\newcommand{\el}{\end{lemma}}
\newcommand{\br}{\begin{rmk}}
\newcommand{\er}{\end{rmk}}
\newcommand{\bc}{\begin{coro}}
\newcommand{\ec}{\end{coro}}
\newcommand{\bd}{\begin{defn}}
\newcommand{\ed}{\end{defn}}
\newcommand{\bex}{\begin{examp}}
\newcommand{\eex}{\end{examp}}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\bp}{\begin{prop}}
\newcommand{\ep}{\end{prop}}
\newcommand{\bce}{\begin{center}}
\newcommand{\ece}{\end{center}}
\newcommand{\bxc}{\begin{xca}}
\newcommand{\exc}{\end{xca}}
\newcommand{\ul}{\underline}
\newcommand{\ol}{\overline}
\newcommand{\ink}{\rule{.8ex}{1.5ex}}   %end of proof marker
\newcommand{\Llr}{\Longleftrightarrow}
\newcommand{\Lr}{\Leftrightarrow}
\newcommand{\imp}{\Longrightarrow}
\newcommand{\sm}{\setminus}
\newcommand{\seq}{\subseteq}
%\newcommand{\C}{\mathfrak c}
\newcommand{\C}{\frak c}
%\renewcommand{\chaptername}{SECTION}
%\renewcommand{\appendixname}{APPENDIX}
%\renewcommand{\bibname}{REFERENCES}
\renewcommand{\contentsname}{TABLE OF CONTENTS}

\renewcommand{\thefigure}{\thesection.\arabic{figure}}
\renewcommand{\thetable}{\thesection.\arabic{table}}

%--------------from the book format----------------------

%\newcommand{\pinch}{\vspace{-9pt}}
\pagenumbering{roman}

\begin{document}
\begin{publicity}%{}


\begin{center}
\vspace{.4in}
{\Large \bf DIMACS EDUCATIONAL MODULE SERIES}

\vspace{1.0in}

{\Large \bf MODULE 03-4}\\[2mm]
{\Large \bf Planar Linkages: Robot Arms and Carpenters' Rulers}\\
{\large \bf Date prepared:} \today

\vspace{.5in}

{\bf Nancy Lineken Hagelgans}\\
{\bf Department of Mathematics and Computer Science}\\
{\bf Ursinus College }\\
{\bf Collegeville, PA 19426}\\
{\bf email: NHagelgans@Ursinus.edu}

\end{center}
\vfill

\end{publicity}

\setcounter{page}{0}
\newpage

\begin{center}
{\large \bf Module Description Information}
\end{center}

\begin{itemize}
\item {\bf Title:}

\textbf {Planar Linkages: Robot Arms and Carpenters' Rulers}

\item {\bf Author(s):}

Nancy Lineken Hagelgans

\item {\bf Abstract:}

A robot arm in the plane is defined as a planar linkage with links
connected to form a chain and with one end in a fixed position.  We
address questions related to the region in the plane that the arm's
other end can reach either with or without obstructions to the arm's
movement.  A carpenters' ruler is another planar linkage in the form
of a chain, but a ruler has no fixed end.  The question investigated
is the minimal folding length of a ruler that has links of different
lengths.

\sk
Exercises throughout the module should be completed as they appear in
the module.  These exercises introduce students to the main ideas
through specific examples.  More challenging problems appear at the
ends of Sections 3, 4, and 5.

\item {\bf Target Audience:}

This module is suitable for mathematically advanced high school
students as well as college mathematics students.

\item {\bf Prerequisites:}

The prerequisite knowledge is high school geometry, sigma notation,
and proof by mathematical induction.

\item {\bf Topics and Goals:}

The topics are two problems involving planar linkages: the
reachability region of a robot arm in the plane and the minimal
folding of a carpenters' ruler.  The goals are to introduce the
concepts of planar linkages and to illustrate proof by mathematical
induction in a geometric context.

\item {\bf Anticipated Number of Class Meetings:}

The entire module would take six class meetings.  Sections 1 through 3
could be used alone for two class meetings.  The first three sections
could be followed by either Section 4 or Section 5, each of which
would involve two class meetings.  On the other hand, the module is
suitable for independent student projects with little or no class time
devoted to the material.


\item {\bf Contact Information:}
Nancy Lineken Hagelgans \\
Department of Mathematics and Computer Science \\
Ursinus College \\
Collegeville, PA 19426 \\
email: NHagelgans@Ursinus.edu

\item {\bf Other DIMACS modules related to this module:}

None at this time

\end{itemize}

\newpage
\setcounter{page}{0}
\pagenumbering{arabic}
\tableofcontents

\newpage
\section*{ABSTRACT}
\addcontentsline{toc}{section}{Abstract}
A robot arm in the plane is defined as a planar linkage with links
connected to form a chain and with one end in a fixed position.  We
address questions related to the region in the plane that the arm's
other end can reach either with or without obstructions to the arm's
movement.  A carpenters' ruler is another planar linkage in the form
of a chain, but a ruler has no fixed end.  The question investigated
is the minimal folding length of a ruler that has links of different
lengths.

\sk
Exercises throughout the module should be completed as they appear in
the module.  These exercises introduce students to the main ideas
through specific examples.  More challenging problems appear at the
ends of Sections 3, 4, and 5.

\newpage
\setcounter{section}{0}
\section{Introduction}
Robot arms are pervasive in the scientific and manufacturing world of
today.  They perform feats that would be impossible or impractical
without their help.  Robot arms have retrieved material and taken
pictures under the oceans as well as on the moon and on Mars.  A robot
arm can work with radioactive materials while people stand behind
protective shields.  In this module, we will explore the extent of a
robot arm restricted to the plane.  This is known as the reachability
problem.

Carpenters' rulers are devices used to measure lengths.  The real
rulers have hinged parts all of the same length.  These rulers can be
folded to the length of just one part, and then they can be partially
or totally unfolded according to the length to be measured.  Thus a
carpenter can carry a relatively small tool that can be expanded to
measure much greater lengths, such as the length of a wall of a room.
We extend the definition of such a ruler to address rulers whose parts
vary in length.  For these rulers, we explore the folding problem: the
problem of folding the ruler to as small a length as possible.

The two devices we study are examples of planar linkages.  They
comprise rigid rods linked together to form a chain.  In the study of
robot arms, we assume that one end of the arm is in a fixed position,
and we are interested in finding all points in the plane that the
other end can reach.  We first consider an arm with only one link, and
then we go on to discuss robot arms with joints.  Finally, we examine
carpenters' rulers, chains of rigid rods with no fixed joints.

\section{Jointless Robot Arms}

Suppose that a robot arm has no joints.  We can consider this arm to
be a rigid rod with a fixed end $J_0$, which is called the {\em
shoulder}.  The other end, $J_1$, moves freely only in a plane.
Intuitively, we think of the end $J_1$ having an attached pen to put a
mark or a tool to do some work.  The robot arm's length is $L$, and
the counterclockwise angle at $J_0$ from the horizontal line through
$J_0$ to the arm is angle $A$.

\begin{center}
\resizebox*{!}{1.2in}{\includegraphics{f21.eps}}

Figure 2.1
\end{center}

\sk
\noindent{\bf Exercises}
\begin{enumerate}
\item[2.1] Estimate the size of angle $A$ in Figure 2.1.

\item[2.2] Sketch a jointless arm with length $L$ of $2$ inches and angle $A$
of $135$ degrees.  Label the angle A and points $J_0$ and $J_1$.
	
\item[2.3] Now suppose that the $2$-inch robot arm has its shoulder placed at
the origin of a coordinate system in the plane and that the arm can
freely rotate about this fixed point.  Which of the following points
can the robot arm reach, i.e., which points can the end $J_1$ reach?
If the point can be reached, what is the angle $A$?

a.  $(2, 0)$

b.  $(0, 2)$

c.  $(-1.5, 0)$

d.  $(\sqrt{2}, -\sqrt{2})$

\item[2.4] A one-link arm of length $2$ has its shoulder $J_0$ placed at the
origin of its plane.  Find the location of its other end $J_1$ given
each of the following angles A.  

a. $A = 90^\circ$

b. $A = 270^\circ$

a. $A = 135^\circ$

\item[2.5] Sketch and describe the set of points in the plane that the
$2$-inch arm can reach.

\end{enumerate}

Exercise 2.3 above gives examples of the {\em reachability problem}
for a robot arm of one link: given the length $L$, the position of the
shoulder $J_0$, and a point $P$ in the plane, can the arm reach the
point $P$, and if so, what is the angle $A$?  In Exercise 2.5, you
found the arm's {\em reachability region}, the set of points reachable
by the arm.  The theorem below describes this reachability region for
a given one-link arm.

\begin{thm}
The reachability region of a one-link arm is the
circle with radius the length $L$ and with center the shoulder $J_0$.
\end{thm}

Now we assume that there are obstructions in the plane that may
prevent free movement of the arm.

\sk
\noindent{\bf Exercises}
\begin{enumerate}

\item[2.6] Let $R$ be a one-link arm of length $2$ with the shoulder
$J_0$ at the origin and with the other end $J_1$ initially at the
point $(2,0)$.  Find and sketch the reachability region if poles or
pegs perpendicular to the arm's plane are located at the indicated
points and obstruct the arm's motion in the plane.  In particular,
assume that the arm cannot move through a pole located in its
reachability region.

a.  $(0, -2)$

b.  $(\sqrt 2, \sqrt 2)$ and $(-2, 0)$

c.  $(0, 2)$, $(-2, 0)$, and $(0, -2)$

d.  $(1, 1)$ and $(\sqrt 3, -\sqrt 3)$

\item[2.7] What effect does the addition of obstructing poles have on
the reachability region?  What is the shape of the reachability region
when one or more poles obstruct the motion of the arm?
	
\item[2.8] The reachability region of a one-link arm of length $3$ is
an open semicircle with endpoints at the points $(1, 3)$ and $(1,
-3)$.  Where is the arm's shoulder located?  Find an initial position
and a smallest set of obstructing poles within the reachability region
of a freely moving arm.
\end{enumerate}

In the next two sections we go on to discuss the reachability region
in the plane of robot arms with more than one link.  We keep in mind
that, with one end of a link fixed, the other end of the link moves to
any point in a specific circle if the motion is unobstructed.

\section{Robot Arms with Two Links}

Now we consider robot arms of two rigid links.  An end of one link is
attached to an end of the other link at the joint $J_1$ as shown in
Figure 3.1.  The shoulder $J_0$ of a robot arm is fixed, and otherwise
the entire arm can move freely in a plane.  The links are allowed to
pass over each other.

\begin{center}
\resizebox*{!}{1.8in}{\includegraphics{f31.eps}}

Figure 3.1
\end{center}

\sk
\noindent{\bf Exercises}
\begin{enumerate}
\item[3.1] Suppose that $R$ is a $2$-link robot arm, and that $R'$ is
another $2$-link robot arm with the same shoulder but with the links
interchanged.  Explain how the parallelogram of Figure 3.2 shows that
a point $P$ in the plane is reachable by arm $R$ if and only if it is
reachable by arm $R'$.
\end{enumerate}

\begin{center}
\resizebox*{!}{1.8in}{\includegraphics{f32.eps}}

Figure 3.2
\end{center}

You have just proved the following theorem.

\begin{thm}
Two-link robot arms with the same shoulder and same link lengths (in
either order) have the same reachability region.
\end{thm}

The lengths of the links of a two-link arm are called $L_1$ and $L_2$
so that $L_1$ is the length of the link with joints $J_0$ and $J_1$,
and $L_2$ is the length of the link with joints $J_1$ and $J_2$.  The
angles involved are the counterclockwise angle $A_1$ at $J_0$ from the
horizontal line through $J_0$ to the first link, and the
counterclockwise angle $A_2$ at $J_1$ from the first link to the
second link.  These lengths and angles are shown in Figure 3.3.

\begin{center}
\resizebox*{!}{1.6in}{\includegraphics{f33.eps}}

Figure 3.3
\end{center}

The {\em reachability problem} for $2$-link robot arms can be stated
as follows: given the lengths $L_1$ and $L_2$, the shoulder $J_0$, and
a point $P(x_0,y_0)$ in the plane, can the robot arm reach the point
P, and if so, which counterclockwise angles $A_1$ and $A_2$ allow P to be
reached?

\sk
\noindent{\bf Exercises}
\begin{enumerate}
\item[3.2] Suppose that a $2$-link arm $R$ with link lengths $L_1= 2$
and $L_2 = 1$ has shoulder at the origin.

a.  Solve the reachability problem given the arm $R$ and each of the
following points.  Plot on one graph and label those points that are
reachable.  
\begin{enumerate}
\item[i.] $(3, 0)$
\item[ii.] $(1, 0)$
\item[iii.] $(0, 1/2)$
\item[iv.] $(0, 4)$
\item[v.] $(\sqrt 2,\sqrt 2)$
\end{enumerate}

b.  Plot and label at least five additional points in the reachability
region on the graph of part a.  For each point, give the two angles
$A_1$ and $A_2$.

c.  Suppose that not only is the shoulder fixed at the origin but that
also the joint $J_1$ is fixed at the point with $x$-coordinate $1$.
Then what is the reachability region?  Sketch the arm and the
reachability region.  

d.  On the same graph sketch the different reachability regions when
the joint $J_1$ is fixed at each of five different points.  

e.  On a new graph sketch the reachability region of the arm $R$ when
$J_1$ is free to move and only the shoulder $J_0$ is fixed.

\item[3.3] Suppose that a $2$-link arm $R$ with link lengths $L_1= 1$ and
$L_2 = 2$ has shoulder at the origin.  Sketch and describe $R$'s
reachability region.  Hint: Review Theorem 3.1.

\item[3.4] Suppose that a $2$-link arm $R$ with link lengths $L_1= 2$ and
$L_2 = 3$ has shoulder at the origin.  Find the point reached with
each pair of given angles.  Sketch.  

a. $A_1 = 90^\circ$ and $A_2 = 90^\circ$

b. $A_1 = 180^\circ$ and $A_2 = 90^\circ$  

c. $A_1 = 90^\circ$ and $A_2 = 180^\circ$

d. $A_1 = 90^\circ$  and $A_2 = 0^\circ$  

e. $A_1 = 45^\circ$ and $A_2 = 180^\circ$

\item[3.5] Is it ever possible for a $2$-link arm $R$ to reach a point in
more than one way, i.e., with different angles $A_1$ and $A_2$?
Explain and give specific examples.

\item[3.6] Describe all $2$-link robot arms with the reachability region
shown in Figure 3.4.  (The description of an arm consists of the
position of the shoulder and the lengths of the links listed in
order.)  The inner circle has radius $1$ and center at the origin.

\begin{center}
\resizebox*{!}{1.6in}{\includegraphics{f34.eps}}

Figure 3.4
\end{center}

\item[3.7] Suppose that you are given a circle $C$ of radius $1$ and a circle
$C'$ of radius $3$.

a.  How many intersection points of these two circles could occur when
the circles are placed at various positions in the plane?

b.  Sketch the two circles in various relative positions in the plane
to illustrate all the possible cases (for $0$, $1$, $2$, or possibly
more intersection points).

c.  Let $A$ be the region in the plane bounded by the two circles with
centers at the center of $C'$ and with radii $2$ and $4$, respectively.
(The region $A$ is an {\em open annulus} with inner radius $2$ and outer
radius $4$.)
\begin{enumerate}
\item[i.] In which of your illustrations in part b. does the center of the
circle $C$ lie on the circle with radius $2$?  Explain.  
\item[ii.] In which of your illustrations in part b. does the center of the
circle $C$ lie on the circle with radius $4$?  Explain.
\item[iii.] In which of your illustrations in part b. does the center of the
circle $C$ lie within the annulus $A$?  Explain.
\end{enumerate}
\end{enumerate}

The examples that you have explored in the exercises illustrate the
reachability region of a 2-link robot arm.  As we see in Figure 3.4,
this region is a {\em closed annulus}, two concentric circles and the
region between these circles.  The common center is the position of
the arm's shoulder.  The smaller radius ({\em inner radius ri}), is
the absolute value of the difference $L_1 - L_2$, and the larger
radius {\em (outer radius ro}) is the sum of these lengths: 
\[
ri = |L_1 - L_2|,\mbox{ and }ro = L_1 + L_2.
\]

We will consider a disk to be a degenerate annulus with $ri = 0$ so
that the case where $L_1 = L_2$ does not need to be treated
separately.

The proof of Theorem 3.2 justifies these statements.

\begin{thm}
The reachability region of a $2$-link robot arm is a closed annulus
centered at the shoulder.  The inner radius $ri = |L_1 - L_2|$, and
the outer radius $ro = L_1 + L_2$.
\end{thm}
{\it Proof\ } We can assume that $L_1\geq L_2$ without loss of
generality by Theorem 3.1.  In this case we want to show that the
inner radius $ri = L_1 - L_2$.

Let $P$ be a point in the plane.  Let $C$ be the circle with radius
$L_2$ and center $P$, and let $C'$ be the circle with radius $L_1$ and
center $J_0$.  See Figure 3.5.  Because the arm's first link has
length $L_1$, the joint $J_1$ must lie on the circle $C'$.  Since the
arm's second link has length $L_2$, the arm reaches the point P only
when $J_1$ lies on the circle $C$.  Thus, the point $P$ is reached if
and only if $J_1$ lies on both circles, i.e., if and only if the two
circles intersect (at a point where $J_1$ can be placed, as shown in
Figure 3.6).  The two circles intersect if and only if $P$ lies in the
required closed annulus.  Therefore, $P$ is reachable if and only if
$P$ lies within this annulus. $\Diamond$

\begin{center}
\resizebox*{!}{2in}{\includegraphics{f35.eps}}

Figure 3.5
\end{center}
\begin{center}
\resizebox*{!}{2in}{\includegraphics{f36.eps}}

Figure 3.6
\end{center}

When a $2$-link arm moves without obstructions in the plane and
without constraints on the angles, all points of the outer circle of
the annular reachability region are reached by extending the arm
fully, i.e., with angle $A_2$ equal to $180^\circ$.  Similarly, all
points of the inner circle are reached by folding the second link back
over the first link, i.e., with zero angle $A_2$.

In the next exercises we will impose conditions that may reduce the
reachability region.

\sk
\noindent{\bf Exercises}
\begin{enumerate}
\item[3.8] A $2$-link robot arm has shoulder at the origin.  Its link
lengths are $L_1 = 5$ and $L_2 = 2$.

a.  Describe the reachability region if there are no obstructions to
movement in the plane.

b.  Describe the reachability regions when obstructing poles are
placed at the following points.  Answer the question for different
initial positions of the arm.
\begin{enumerate}
\item[i.] $(0, 2)$
\item[ii.] $(0, 4)$
\item[iii.] $(0, 8)$
\item[iv.] $(0, 4)$ and $(0, 7)$
\item[v.] $(0, 4)$ and $(-4, 0)$
\end{enumerate}

c.  Describe the reachability regions when the following restrictions
are placed on the arm's joint angles.
\begin{enumerate}
\item[i.] $0 \leq A_1 \leq  180^\circ$
\item[ii.] $90^\circ \leq A_2\leq 180^\circ$
\end{enumerate}
\end{enumerate}

\sk
\noindent{\bf Problems}
\begin{enumerate}
\item[3.1] Sketch and describe the reachability region of a 2-link
robot arm when one, two, or more obstructing poles are placed at
various points in the plane.
	
\item[3.2] Sketch and describe the reachability region of a 2-link arm
when one or both of its joint angles are restricted to intervals with
endpoints $a$ and $b$, where $0 \leq a < b < 360$ degrees.
	
\item[3.3] A $2$-link arm has reachability region shown in Figure
3.7. The inner circle has radius $1$ and center at the origin.
Suppose that only part of this annulus (as described below) is wanted
for the reachability region.  With this robot arm, describe a minimal
set of obstructing poles that yields each reachability region listed
below (whenever possible).  Also state restrictions on the joint
angles that yield these regions (whenever possible).  Explain and
justify your answers.

\begin{center}
\resizebox*{!}{1.8in}{\includegraphics{f37.eps}}

Figure 3.7
\end{center}

a.  the upper half of the annulus, and the lower halves of the two
disks with radii $2$ and centers $(\pm 3, 0)$

b.  the part of the annulus of at most distance 3 from the origin

c.  the part of the annulus of at least distance $\sqrt{13}$ from the
origin

d.  the part of the annulus in the first and third quadrants

e.  some other regions of different types
\end{enumerate}

\section{Multi-link Robot Arms}

Now that we have investigated the properties of robot arms with either
one link or two links, we move on to consider arms with any number of
links.  We assume that each arm has $n$ links, where $n\geq 1$, and that
the shoulder $J_0$ is fixed at the origin.  Except for the shoulder,
we assume that the arm moves freely in the plane, and the links may
pass over each other.  Later we will restrict the motion in various
ways.  Our main concern is the reachability region.

\medskip
We will use the following notation for $n$-link robot arms:
\begin{enumerate}
\item The ends of the links (the joints): $J_0,J_1,\dots, J_n$
\item The counterclockwise angles: $A_1$ from the horizontal to the
first link, and $A_i$ from the $(i-1)^{\rm st}$ link to the $i^{\rm th}$
link for $i = 2, 3,\dots,n$
\item The length of the $i^{\rm th}$ link: $L_i$
\end{enumerate}

{\flushleft A 4-link arm is shown in Figure 4.1.}

\begin{center}
\includegraphics{f41.eps}

Figure 4.1
\end{center}

\sk
\noindent{\bf Exercises}
\begin{enumerate}
\item[4.1] Suppose that the link lengths of a $3$-link arm are $1$,
$2$, and $3$.

a.  In how many different ways can an arm be constructed with these
links?

b.  Consider the arms with link lengths shown in the table below.

\begin{tabular}{cccc}
		       Arm&	$L_1$&	   $L_2$&	$L_3$\\
\hline			$R_1$&	1&	   2&	3\\
			$R_2$&	1&	   3&	2\\
			$R_3$&	3&	   2&	1
\end{tabular}

Sketch diagrams to show that a point $P$ in the plane is either
reachable by all three arms or by none of these three arms.  Hint:
Review Figure 3.2 and Theorem 3.1.

\item[4.2] Now suppose that the link lengths of a $4$-link arm are
$1$, $2$, $4$, and $5$.  Suppose that $R$ is an arm in which the link
lengths occur in ascending order, and suppose that $R'$ is an arm for
which these lengths occur in descending order.  Let $P$ be a point
reachable by $R$.  Construct a sequence of arms with these lengths
that all reach $P$.  The first arm in the sequence is $R$, and the
last arm is $R'$.  In addition, the next arm is obtained at each step
by interchanging only two adjacent link lengths.  For example, the
second arm could have link lengths $1$, $2$, $5$, $4$ in that order by
interchanging only the last two links.  Explain why $P$ is reachable
by each arm in the sequence and sketch supporting diagrams.
\end{enumerate}

In the preceding exercises, different arrangements of given links form
robot arms with the same reachability regions.  We will show rather
remarkably that the link lengths rather than the order in which the
links are assembled determine the reachability region of any $n$-link
arm.  Later we will find it useful to consider those robot arms that
have the longest link first.

\begin{thm}
Any two n-link robot arms with the same set of link lengths have
identical reachability regions.  [OR, page 325]
\end{thm}
{\it Proof\ } Recall that consideration of a parallelogram led to the
conclusion that two $2$-link arms with the same link lengths have the
same reachability region (Exercise 3.1).  We apply this idea to see
that any two links of a robot arm can be interchanged without
affecting the reachability region.  Let $R$ and $R'$ be any two $n$-link arms
with the same set of link lengths.  Then there is a sequence of arms
starting with $R$ and ending with $R'$ such that a new arm in the
sequence is obtained from the previous arm by interchanging the order
of exactly two adjacent link lengths.  Thus $R$ and $R'$ have the same
reachability region. $\diamondsuit$

\sk
\noindent{\bf Exercises}
\begin{enumerate}
\item[4.3] A $3$-link robot arm $R$ has link lengths $L_1 = 5$, $L_2 =
2$, and $L_3 = 1$.

a.  Describe and sketch the reachability region of the $2$-link arm
formed from the first two links of $R$.

b.  Choose $10$ points $P$ within the reachability region (of the
$2$-link arm of part a.) and $5$ points $P$ on the boundary of this
reachability region.  For each of these $15$ points $P$, sketch a
circle of center $P$ and radius $1$.  How are these circles related to
the $3$-link arm $R$?

c.  Describe and sketch the reachability region of the arm $R$.
	
\item[4.4] Answer the questions of Exercise 4.3 for a $3$-link robot
arm with link lengths $L_1 = 4$, $L_2 = 3$, and $L_3 = 3$.
	
\item[4.5] Why do you obtain different results for the two $3$-link
robot arms of the preceding exercises?
\end{enumerate}

Notice that the longest link is the first link in the arms
investigated in the Exercises 4.3 and 4.4.  The next theorem
explicitly states the conditions that determine whether the
reachability region is an annulus with $ri > 0$ or a disk (an annulus
with $ri = 0$).  The theorem relates the radii $ri$ and $ro$ to the
link lengths.

\begin{thm}
The reachability region of a robot arm with $n$ links, where $n > 1$,
is an annulus centered at the origin with the following properties:
\begin{enumerate}
\item the outer radius $ro$ equals the sum of the link lengths: $ro
=\sum_{i=1}^nL_i$, and
\item the inner radius $ri$ equals the largest link length $L_M$ less
the sum of the other link lengths if this difference is not negative,
and otherwise $ri$ equals zero:
\end{enumerate}
\[
ri = \max \{0, L_M -\sum_{i\neq M}L_i \}. \mbox{ [OR, page 326; HJW85,
page 318]}
\]
\end{thm}
{\it Proof\ } (by induction on $n$) The theorem holds for any 2-link
arm by Theorem 3.2 .  Let $n > 1$, and assume that the theorem holds
for any $n$-link arm.  Let $R$ be an $(n+1)$-link arm with link lengths
$L_1, L_2,\dots,L_n, L_{n+1}$. Without loss of generality, by Theorem
4.1, we can assume that the link lengths occur in descending order.
Then the longest link is the first link.  Let $R'$ be the $n$-link arm
constructed by deleting the last (and smallest) link from the arm $R$.
Then, by the inductive hypothesis, the reachability region of $R'$ is
an annulus centered at the origin such that:

1.  the outer radius $ro =\sum_{i=1}^nL_i$ , and

2.  the inner radius $ri = \max \{0, L_1 - \sum_{i=2}^nL_i\}$.

Let $P$ be a point in the plane, and denote $P$'s distance from the
origin by $|P|$.  Then $P$ is not reachable by the arm $R$ if $|P| >
\sum_{i=1}^{n+1}L_i$ since $R$ can reach only the distance $L_{n+1}$ from the
reachable points of $R'$ of greatest distance from the origin.
Similarly, $P$ is not reachable by the arm $R$ if $|P| < L_1
-\sum_{i=2}^{n+1}L_i$ since $R$ can reach only the distance $L_{n+1}$
from the reachable points of $R'$ closest to the origin.  For $P$ at
any other location in the plane, the circle with center at $P$ and
with radius $L_{n+1}$ has at least one intersection point with the
reachability region of $R'$.  Therefore, the reachability region of
$R$ is the required annulus. $\diamondsuit$
 
\begin{coro}
The following three conditions on an $n$-link arm $R$ are equivalent:

1. $R$'s reachability region has inner radius $ri = 0$,

2. $L_M\leq\sum_{i\neq M}L_i$ , where $L_M$ is $R$'s largest link
   length, and

3. $L_M \leq L/2$, where $L = \sum_{i=1}^nL_i$.
\end{coro}
{\it Proof } The equivalence of the first two conditions follows
immediately from the expression of $ri$ as a maximum.  To show that
the second and third condition are equivalent, add $L_M$ to both sides
of the inequality of the second condition, and then divide by $2$.
$\diamondsuit$

Once we know that a point is reachable by a robot arm, we would like
to consider different configurations of the arm that allow the arm to
reach that point.  In particular, we know that any point of the outer
bounding circle can be reached in only one way, and all the joint
angles except the one at the shoulder are $180$ degrees in this
solution.  On the other hand, if the link of maximum length is the
first link and $r_i > 0$, 
a point of the inner bounding circle is reached with the
joint angle $J_1$ equal to $0$ degrees and the other joint angles,
except the shoulder angle, equal to $180$ degrees.  We are especially
interested in $180$ degree joint angles because the two links meeting
at these joints can be considered to be only one link rather than two
links.

\sk
\noindent{\bf Exercises}
\begin{enumerate}
\item[4.6] Consider a $7$-link robot arm $R$ with link lengths $3$,
$6$, $5$, $2$, $2$, $4$, and $2$ in that order.

a.  Sketch the reachability region of the arm $R$.

b.  Compute the sum $L$ of $R$'s link lengths.  How is this sum
related to the reachability region?

c.  We want to find a particular link called the {\em median link (of
length $L_m$)}.  Begin adding the link lengths starting at the
shoulder ($3 + 6 + \dots$), and stop adding when this sum is greater
than $L/2$, where $L$ is the total length found in part b.  The link
whose length puts the cumulative sum greater than $L/2$ is the median
link.  What is its length?

d.  Sketch a horizontal line segment of length $6$ inches.  Consider
this line to represent the arm fully extended, i.e., with 180 degree
joint angles.  What is the length on the line that represents one unit
in the measurement of the robot arm?  Sketch a vertical line segment
at the midpoint of the $6$-inch line segment.  How is this vertical
line related to the median link?  Explain.

e.  Let $R'$ be the $3$-link robot arm obtained from $R$ by fixing
$R$'s joint angles at $180$ degrees with the exception of angles
$A_1$, $A_{m-1}$, and $A_m$.  Then only three joints can be varied:
the shoulder joint $J_0$ and the two joints at the ends of the median
link.
\begin{enumerate}
\item[i.] What are the three link lengths of the arm $R'$?
\item[ii.] Sketch the reachability region of $R'$.  How is this region
related to the reachability region of the arm $R$?
\end{enumerate}

\item[4.7] Let R be a $6$-link robot arm with link lengths $3$, $2$,
$2$, $1$, $10$, and $1$ in that order.

a.  Sketch the reachability region of the arm $R$.

b.  Compute the sum $L$ of $R$'s link lengths.  How is this sum
related to the reachability region?

c.  Find the length $L_m$ of the median link.

d.  How is $L_m$ related to $L_M$?

e.  Let $R'$ be the $3$-link robot arm obtained from $R$ by fixing
$R$'s joint angles at $180$ degrees with the exception of angles
$A_1$, $A_{m-1}$, and $A_m$.  Then only three joints can be varied:
the shoulder joint $J_0$ and the two joints at the ends of the median
link.
\begin{enumerate}
\item[i.] What are the three link lengths of the arm $R'$?
\item[ii.] Sketch the reachability region of $R'$.  How is this region
related to the reachability region of the arm $R$?
\end{enumerate}
\end{enumerate}

The two multi-link arms of the preceding exercises illustrate the two
cases: zero and nonzero inner radius of the reachability region.  In
both examples, you were able to find a $3$-link robot arm with the
same reachability region as that of the given arm.  In fact, we will
show (in the next theorem) that every robot arm has the same
reachability region as an arm with only $2$ or $3$ links.  First we
consider some useful relations involving the link lengths $L_m$ and
$L_M$.

\begin{lemma}
Let $L_m$ be the median link length and $L_M$ the maximum link length of a
robot arm.  If $ri > 0$, then $M = m$.
\end{lemma}
{\it Proof\ } Suppose that $ri > 0$.
Then, by Corollary 4.3, $L_M > L/2$.  Thus the longest
link cannot be any link other than the median link, i.e., $M = m$. 
$\diamondsuit$

\begin{thm}
Suppose that $n > 1$ and that $R$ is an $n$-link robot arm with link
lengths $L_1, L_2, \dots, L_n$.

1.  If the median link is not the first link or last link, then $R$
has the same reachability region as a $3$-link arm $R'$ with link
lengths $\sum_{i=1}^{m-1}L_i$, $L_m$, and $\sum_{i=m+1}^nL_i$.

2.  If the median link is either the first link or the last link, then
$R$ has the same reachability region as a $2$-link arm $R'$ with link
lengths $L_m$ and $\sum_{i\neq m}L_i$. [OR, page 329]
\end{thm}
{\it Proof\ } The reachability region of each robot arm mentioned is
an annulus centered at the origin with outer radius $ro =
\sum_{i=1}^nL_i$.  Thus it remains to check only the inner radii.  Let
$ri$ be the inner radius of the reachability region of the $n$-link
arm $R$.  We consider the two possible cases: positive and zero inner
radius $ri$.

Suppose that $ri > 0$.  Then $M = m$ by Lemma 4.4.  So the robot arm
constructed from $R$ by fixing all but the required two or three
joints to 180 degrees, has the maximum link length $L_M$ and thus the
same inner radius,
\[
L_M -\sum_{i\neq M}L_i,
\] 
of its reachability region.

Now suppose that $ri = 0$.  Then $L_M \leq L/2$ by Corollary 4.3. Also,
by definition of the median link, $\sum_{i=1}^{m-1}L_i< L/2$ and
$\sum_{i=m+1}^nL_i < L/2$.  Therefore, whether or not the longest link
length of $R'$ is $L_M$, the longest length 
of $R'$ is less than or equal to $L/2$.
So, by Corollary 4.3 applied to $R'$, the inner radius for $R'$ is
zero.

Thus, in both cases, the reachability regions of the robot arms $R$
and $R'$ are identical. $\diamondsuit$

\medskip
We will find that the arms with 2 or 3 links help us to determine
reachability regions when the other arms are unable to move freely.

\sk
\noindent{\bf Exercises}
\begin{enumerate}
\item[4.8] A $3$-link robot arm $R$ has link lengths $L_1 = 3$, $L_2 =
7$, and $L_3 = 2$.  Sketch and describe its reachability region when
obstructing poles occur at the following points.  There may be several
regions determined by different initial positions of the arm.

a.  $(1, 0)$

b.  $(3, 0)$

c.  $(5, 0)$

d.  $(1, 0)$ and $(0, 5)$

e.  $(1, 0)$, $(0, 5)$, and $(-3, 0)$
	
\item[4.9] A $5$-link robot arm has link lengths $2$, $1$, $6$, $1$,
and $1$ in that order. Sketch and describe its reachability region
when obstructing poles occur at the points given in the preceding
problem.
	
\item[4.10] A $3$-link robot arm has link lengths $L_1 = 3$, $L_2 =
7$, and $L_3 = 5$.  Sketch and describe its reachability region when
obstructing poles occur at the following points.

a.  $(1, 0)$

b.  $(4, 0)$

c.  $(1, 0)$ and $(0, 4)$
\end{enumerate}

\sk
\noindent{\bf Problems}
\begin{enumerate}
\item[4.1] Let $R$ be a $3$-link robot arm with link lengths $L_1$,
$L_2$, and $L_3$ and with reachability region the closed annulus $A$.

a.  Sketch and describe the annulus $A$.  Indicate $L_1$, $L_2$, and
$L_3$.  On this sketch indicate the region reached when the joint
$J_1$ is in a fixed position.  Hint: There are several cases.

b.  In how many different configurations can the arm $R$ reach a point
$P$ on the boundary of $A$?  Explain.

c.  In how many different configurations can the arm $R$ reach a point
$P$ in the interior of $A$?  Describe the joint angles $A_1$ that make
it possible for the arm $R$ to reach $P$.
	
\item[4.2] Sketch and describe the reachability region of a $3$-link
robot arm when one or two obstructing poles are placed at various
positions in the plane.

\item[4.3] Sketch or describe the reachability region of a $3$-link
robot arm when its joint angles are restricted to certain intervals.
\end{enumerate}

We return to the {\em reachability problem}, and now we consider robot
arms with any number of links.  The general problem can be stated as
follows: given the link lengths of a robot arm, the shoulder $J_0$,
and a point $P(x_0,y_0)$ in the plane, can the robot arm reach the
point $P$, and if so, which joint angles allow $P$ to be reached?
Since we know that the reachability region of a robot arm is a closed
annulus centered at the shoulder (by Theorem 4.2), we can readily
determine whether or not the point $P$ is reachable by computing its
distance from the shoulder.  We also know the unique angles when the
point $P$ lies on the boundary of the annulus.  In general, the number
of sets of joint angles that allow an arm to reach a point $P$ in the
interior of the annulus is larger for a larger number of links, i.e.,
there are more configurations possible.  Some of these angles can be
found by applying Theorem 4.6 and its proof.

\sk
\noindent{\bf Problems}
\begin{enumerate}
\item[4.4] A $3$-link robot arm $R$ has link lengths $10$, $4$, and
$2$ in that order.  Its shoulder lies at the origin.  Solve the
reachability problem for the following points.  Certain angles may be
found by measuring them with a protractor in your carefully drawn
diagram or by using trigonometry.  You may use diagrams to indicate
angles when $P$ lies in the interior of the reachability region.  Hint:
Review Figures 3.5 and 3.6 to help you find the configurations when $P$
lies in the interior of the reachability region.

a. $(1, 0)$

b. $(6, 0)$

c. $(8, 0)$

d. $(0, 16)$

e. $(0, 20)$

f. $(5\sqrt 2, 6 - 5\sqrt 2)$

\item[4.5] How would your answers to the questions of Problem 4.4
change for an arm with link lengths $10$, $2$, $2$, and $2$ in that
order?
\end{enumerate}

When we considered robot arms of $2$ links, we saw that each point in
the interior of the reachability region could be reached in two ways,
with two different sets of joint angles.  These problems show us that
there are many ways for a robot arm of more than $2$ links to reach a
point in the interior of its reachability region.

\section{Carpenters' Rulers}

A carpenters' ruler consists of rigid links joined end to end to form
a chain.  The links may cross over each other as they rotate about
their endpoints, which are called the joints.  These rulers are used
to measure lengths, such as the dimensions of a room.  Although a real
carpenters' ruler has links all of the same length, we consider rulers
where the links may differ in length.

We will adopt the notation used earlier for robot arms.  In fact, the
main difference between a robot arm and a carpenters' ruler is that,
unlike the robot arm, a ruler has no fixed end such as the shoulder of
a robot arm.

Let $L_1, L_2, \dots,L_n$ be the link lengths, and let $J_0, J_1, J_2,
\dots,J_n$ be the joints.  As for robot arms, $J_0$ and $J_n$ are the
ends of the device.  A carpenters' ruler with four links is shown in
Figure 5.1.

\begin{center}
\resizebox*{!}{1.3in}{\includegraphics{f51.eps}}

Figure 5.1
\end{center}

A ruler's greatest length is achieved when all the joint angles equal
$180^\circ$.  We will investigate the ruler when folded, that is when
each joint angle is either $0^\circ$ or $180^\circ$.  A folded
$6$-link ruler is indicated in Figure 5.2.  The angle at the joint
$J_4$ is $180^\circ$, and the other joint angles are $0^\circ$.  The
{\em folded length} of the ruler is approximately $L$, as shown in
Figure 5.2.

\begin{center}
\resizebox*{!}{1.2in}{\includegraphics{f52.eps}}

Figure 5.2
\end{center}

\sk
\noindent{\bf Exercises}
\begin{enumerate}
\item[5.1] A carpenters' ruler is to be assembled with links of
lengths $6$, $7$, and $8$ inches.

a.  What is its maximum length?  What joint angles yield this maximum
length?

b.  How many different rulers can be made by joining the links in
different orders?

c.  Fold each ruler (of part b.) so that its folded length is as small
as possible.  Sketch the folded rulers and indicate the smallest
folded length on the sketch.

d.  Are the minimal folded lengths the same for the different rulers
(of part b.)?

\item[5.2] A carpenters' ruler $R$ has link lengths $L_1 = 2$, $L_2 =
3$, $L_3 = 5$, and $L_4 = 1$.

a.  Is it possible to fold the ruler $R$ with folded length $L = 4$?
Explain.

b.  What is the smallest folding length possible?  Sketch all the ways
that $R$ can be folded with the smallest folding length.
\end{enumerate}

The exercises above have shown two properties of carpenters' rulers:
\begin{enumerate}
\item Rulers with the same link lengths but with links assembled in
different order may have different shortest folding length.
\item The shortest folding length of a ruler may be achieved in more
than one way.
\end{enumerate}

We are mainly interested in solving the {\em minimum length folding
problem}: given a carpenters' ruler, find its minimum folding length
and state the joint angles that achieve this length.

The next exercises involve carpenters' rulers with more than three
links.

\newpage
\noindent{\bf Exercises}
\begin{enumerate}
\item[5.3] A carpenters' ruler $R$ has link lengths $L_1 = 3$, $L_2 =
4$, $L_3 = 7$, $L_4 = 4$, and $L_5 = 2$.

a.  What is the longest length of a link?  We will call this {\em
maximum length $L_M$}.

b.  Sketch the ruler $R$ folded using the following method:
\begin{enumerate}
\item[i.] Sketch a horizontal line segment $S$ of length twice $L_M$. 
Assume the units are inches.
\item[ii.] Place $R$'s first link on the segment $S$ as far left as
possible, so $J_0$ is placed on the left endpoint of $S$.
\item[iii.] Place the other links in order according to the following
directions: place the joint $J_i$ to the right of $J_{i-1}$ if the
$i^{\rm th}$ link would still be within the segment $S$; otherwise
place $J_i$ to the left of $J_{i-1}$.
\end{enumerate}

What is the folding length $L$ of the ruler folded in this manner?  Is
$L < 2 L_M$?  Is $L = 2 L_M$?

\item[5.4] Answer the questions of Exercise 5.3 for a carpenters'
ruler with link lengths $L_1 = 4$, $L_2 = 4$, $L_3 = 7$, $L_4 = 3$,
$L_5 = 2$.  (Note that the rulers of Exercises 5.3 and 5.4 have the
same link lengths, but these lengths occur in different orders.)
\end{enumerate}

The folding method described in Exercise 5.3 works for any ruler, and
it gives us an upper bound on the minimal folding length that depends
only on the length of the longest link.

\begin{thm}
If a carpenters' ruler $R$ has longest link length $L_M$, then the
ruler can be folded with folding length less than twice $L_M$.  [HJW85,
page 316]
\end{thm}
{\it Proof\ } (by induction on the number of links) Suppose that the
ruler $R$ has $1$ link.  Then, since $L_1 = L_M < 2L_M$, the ruler
is ``folded'' with folding length $L < 2L_M$.

Now let $n \geq 1$, and suppose that every ruler of $n$ links can be
folded as required.  Let $R$ be a ruler of $n+1$ links.  Then the ruler
$R'$ obtained by removing the last link from $R$ can be folded with
folding length $< 2L'_M$, where $L'_M$ is the length of the longest
link of $R'$.  Then $R'$ is folded with folding length $< 2L_M$.
Use this folding for the ruler $R$ for all but the last joint angle,
and choose the remaining joint angle (at $J_n$) to be $180^\circ$ if
the distance between the end $J_0$ and the joint $J_n \leq L_M$ and to
be $0^\circ$ otherwise.  Then $R$ is folded with folding length 
$< 2L_M$. $\diamondsuit$

This theorem helps us to find a ruler's minimum folding length because
we know that we do not have to consider any folding length greater
than or equal to $2L_M$.  This means that we have to consider only some of the
possible ways of folding the ruler.  The example below illustrates how
these possible ways to fold can be organized in a tree structure.

\bsk
\noindent{\bf Example 5.1\ }
Suppose that a carpenters' ruler $R$ has link lengths $L_1 = 2$, $L_2
= 3$, $L_3 = 3$, and $L_4 = 2$.  We know that the minimal folding
length is less than $2L_M = 2\times 3 = 6$.  Thus, as we consider the
joints in order, we can ignore any placement of a joint that
guarantees a folding length greater than or equal to $6$.  
We start building a tree
of possible ways to fold the ruler by considering joint $J_0$ placed
at the number $0$ on the real number line.  We write $(0, 0)$ at the
root of the tree; the first $0$ means that $J_0$ is placed at $0$, and
the second $0$ means that the folding length so far is $0$.  Next we
place the joint $J_1$ at $2$ on the number line.  Then, since $J_1$
lies to the right of $J_0$, we write a right child $(2, 2)$ of the
root to construct the tree of Figure 5.3.

\begin{center}
%\resizebox*{!}{1.5in}{
\includegraphics{f53.eps}
%}

Figure 5.3
\end{center}

We continue to construct the tree with joint $J_2$, which may be
placed either $3$ units to the left of $J_1$ or $3$ units to the right
of $J_1$.  Figure 5.4 shows the tree with level 2 added.

\begin{center}
%\resizebox*{!}{1.5in}{
\includegraphics{f54.eps}
%}

Figure 5.4
\end{center}

The new positions are obtained by subtracting the link length $3$ from
the position of the joint $J_1$ for the left child and by adding the
link length $3$ to the position of the joint $J_1$ for the right
child.  We compute the folding length so far by looking at all the
joint positions along the path from the root to the current node, and
then subtracting the smallest number from the largest.  For example,
when constructing the left child at level 2, we consider the positions
$0$, $2$, and $-1$, and we find the folding length so far to be $2 -
(-1) = 3$.

The complete tree is shown in Figure 5.5.  We write no children when
we would overstep or equal the upper bound of $6$ on the minimum folding length
of the ruler.  At the next level, we get folding lengths $5$ and $3$
for the two possible angles at joint $J_1$.  Then at the third level,
we have to consider the four possibilities for the third link, which
has length $1$.

\begin{center}
%\resizebox*{!}{1.5in}{
\includegraphics{f55.eps}
%}

Figure 5.5
\end{center}

The tree in Figure 5.5 shows that there are $4$ ways to fold the ruler
to obtain folding length $< 6$ and that the minimal folding length
is $3$.  Notice that this minimal folding length is obtained in only
one way, when every joint angle is $180^\circ$.  Other rulers can be
folded in several different ways to obtain the minimum folding length.

\sk
\noindent{\bf Exercises}
\begin{enumerate}
\item[5.5] Sketch the tree diagram of Example 5.1 when the joint $J_1$
is placed at the point $-2$ instead of at the point $2$.  Why do you
obtain the same result?
	
\item[5.6] Suppose that a $5$-link ruler $R$ has the same first four
link lengths as the ruler of Example 5.1 and link length $L_5 =
3$.  Add the fifth level to the tree diagram of Figure 5.5.  What is
the minimal folding length of the ruler $R$?
	
\item[5.7] Part of the tree diagram to determine minimal length of a
carpenters' ruler $R$ is shown in Figure 5.6.  Some information is
given at every level of this tree.

a.  How many links does the ruler $R$ have?

b.  What are $R$'s link lengths?

c.  Complete the tree.

d.  What is the minimal folding length of $R$?

e.  List the joint angles that achieve this minimal folding length.

\begin{center}
\includegraphics{f56.eps}

Figure 5.6
\end{center}
\end{enumerate}

Now we know that any carpenters' ruler can be folded with folding
length $< 2L_M$.  The next question to ask is whether or not we can
find a better (a lower) upper bound on the minimal folding length.
The next theorem states that $2L_M$ is a {\em tight bound}, i.e., the
best there is.  The next exercise illustrates the type of ruler
defined in the proof of the theorem.

\newpage
%\sk
\noindent{\bf Exercises}
\begin{enumerate}
\item[5.8] A $7$-link carpenters' ruler $R$ has link lengths $L_1 =
L_3 = L_5 = L_7 = 1$ and $L_2 = L_4 = L_6 = 0.99$ so that all the
links with odd subscripts have the same length, and all the links with
even subscripts have the same somewhat shorter length.

a.  Use a tree diagram to determine the minimal folding length of the
ruler $R$.

b.  What are the joint angles when the minimal folding length is
achieved?
\end{enumerate}

\begin{thm}
The upper bound $2L_M$ on the minimal folding length of a carpenters'
ruler is tight, i.e., there is no smaller upper bound. [HJW85, page
317]
\end{thm}
{\it Proof\ } Let $L_M$ be a positive number.  We want to consider the
set of carpenters' rulers with maximum link length equal to $L_M$.  We
ask ourselves if all these rulers have minimal folding length less
than or equal to some number $X$, where $X < 2L_M$.

Suppose that the number $X$ is a candidate for a smaller upper bound
so that
\[
L_M \leq X < 2L_M.
\]
Let $Y$ be the average of $X$ and $2L_M$:
\[
Y = \frac{X+2L_M}{2}
\]

\begin{center}
\resizebox*{5.3in}{!}{\includegraphics{f57.eps}}

Figure 5.7
\end{center}

We will construct a ruler that has maximum link length $L_M$ and
minimum folding length $Y$.  Let $k$ be the smallest integer that is
$\geq \frac{L_M}{2L_M-Y}$, i.e.,
\[
k=\bigg\lceil\frac{L_M}{2L_M-Y}\bigg\rceil
\]

Let $n = 2k - 1$.  Consider an $n$-link carpenters' ruler $R$ with
link lengths: $L_1 = L_3 =\dots=L_n = L_M$ and $L_2 = L_4
=\dots=L_{n-1} = Y - L_M$.

The minimal folding length $L$ is achieved when every joint angle is
$0^\circ$.  The first link has length $L_M$.  If we go through the
links in order after this first link, we can think of a link with an
even subscript along with the next link.  Figure 5.8 illustrates the
first link as well as the pair composed of the second and third links.

\begin{center}
\includegraphics{f58.eps}

Figure 5.8
\end{center}

We see that the pair of links increases the folded length so far by
the difference of the link lengths:
\[
L_M - (Y - L_M) = 2L_M - Y.
\]
Since the first link has length $L_M$ and since there are $k-1$ pairs
of other links, the minimal folding length is:
\begin{eqnarray*}
L_M + (k-1)(2 L_M - Y) &=& L_M + k(2  L_M - Y) - (2  L_M - Y)\\
&=& Y - L_M +  \lceil\frac{L_M}{2L_M-Y}\rceil (2 L_M - Y)\\
&\geq& Y - L_M + L_M = Y > X.
\end{eqnarray*}
The carpenters' ruler that we have described has minimal folding
length $> X$.  Thus $X$ is not an upper bound on the set of minimal
folding lengths.  Therefore the upper bound $2L_M$ is tight.  $\diamondsuit$

\sk
\noindent{\bf Problems}
\begin{enumerate}
\item[5.1] Suppose we consider only those rulers whose link lengths
are integers.  Is the upper bound $2L_M$ on the minimal folding length
tight for these rulers?  Justify your answer.
	
\item[5.2] Describe the reachability region of a robot arm that is
folded (in all possible ways), i.e., all the joint angles except the
shoulder angle are constrained to be either $0^\circ$ or $180^\circ$.
	
\item[5.3] Suppose that a ruler $R$ has integer link lengths $2L$,
$L$, $L_1$, $L_2$,$\dots$,$L_n$, $L$, and $2L$ in that order, where
$L$ is the sum of the integers $L_1$, $L_2$,$\dots$,$L_n$.  Further
assume that the ruler $R$ can be folded with folding length $2L$.
Show that the integers $L_1$, $L_2$,$\dots$,$L_n$ can be placed in two
sets so that the sum of the integers in one set equals the sum of
integers in the other set.  [HJW85, page 316]
\end{enumerate}

\begin{thebibliography}{AAAAA}
\addcontentsline{toc}{section}{\numberline{}References\dotfill}

\bibitem[HJW84]{HJW84} Hopcroft, John; Joseph, Deborah; Whitesides,
Sue.  ``Movement problems for $2$-dimensional linkages."  {\em SIAM
J. Computing} 13(3), 1984, 610 - 629.

\bibitem[HJW85]{HJW85} Hopcroft, John; Joseph, Deborah; Whitesides,
Sue.  ``On the movement of robot arms in $2$-dimensional bounded
regions."  {\em SIAM J. Computing} 14(2), 1985, 315 - 333.

\bibitem[K86]{K86} Kantabutra, V.  ``New Algorithms for Multilink Robot
Arms."  {\em Journal of Computer and System Sciences} 32(1), 1986, 136
- 153.

\bibitem[K92]{K92} Kantabutra, V.  ``Motions of a Short-Linked Robot
Arm in a Square."  {\em Discrete and Computational Geometry} 7, 1992,
69 -76.

\bibitem[OR]{OR} O'Rourke, Joseph.  {\em Computational Geometry in C,
Second Edition.}  Cambridge University Press, 1998.

\bibitem[SY]{SY} Suzuki, Ichiro; Yamashita, Masafumi.  ``Designing
Multi-link Robot Arms in a Convex Polygon." {\em International Journal
of Computational Geometry and Applications} 6(4), 1996, 461 - 486.

\bibitem[W]{W} Whitesides, Sue.  ``Algorithmic issues in the geometry
of planar linkages."  {\em The Australian Computer Journal} 24(2),
1992, 42 - 51.

\end{thebibliography}
\end{document}
