Computational Geometry Column 44
The open problem of whether or not every pair of equal-area polygons has a hinged dissection is discussed.
44.tex
\documentclass{article}
\usepackage{graphicx}
\usepackage{url}

\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{latexsym}

%\def\R{\mathbb{R}}
%\def\e{{\epsilon}}
%\def\a{{\alpha}}
%\def\b{{\beta}}

\input{mac.tex}

%Page dimesions: Unclear what should be used, so all commented out.
%\setlength{\oddsidemargin}{0in}
%\setlength{\topmargin}{-.5in}
%\setlength{\textwidth}{6.6in}
%\setlength{\textheight}{9in}

\title{Computational Geometry Column 44}
\author{%
Joseph O'Rourke\thanks{
Dept. of Computer Science, Smith Col\-lege, North\-ampton, 
MA 01063, USA.
orourke@\allowbreak cs.\allowbreak smith.\allowbreak edu.
Supported by NSF Distinguished Teaching Scholar Grant DUE-0123154.
}
}
\date{}
\begin{document}
\maketitle
%\pagestyle{empty}
%\thispagestyle{empty}

\begin{abstract}
The open problem of whether or not every pair of equal-area polygons
has a hinged dissection is discussed.
\end{abstract}

A \emph{dissection} of one polygon $A$ to another $B$ is a partition of $A$
into a finite number of pieces that may be reassembled to form $B$.
$A$ and $B$ are then said to be \emph{equidecomposable}.
A staple of puzzle collections for centuries, the field has been given new
life through Frederickson's 1997 monograph~\cite{f-dpf-97}.
He quickly followed that with a second book~\cite{f-hdst-02} on \emph{hinged dissections},
the most famous of which is the elegant 1902 Dudeney-McElroy hinged
dissection between a square and an equilateral triangle illustrated in
Fig.~\figref{sq.tri.hinged}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure Begin
\begin{figure}[htbp]
\centering
\includegraphics[width=\linewidth]{sq.tri.hinged.eps}
%\fbox{sq.tri.hinged.eps}
\caption{A four-piece hinged dissection between a square and an equilateral triangle.}
\figlab{sq.tri.hinged}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure End

It has been known since the early 19th century that any two polygons of equal
area are equidecomposable.\footnote{
  It has been known since the early 20th century that not all equal-volume
  polyhedra are equidecomposable.}
One method~\cite[p.~221]{f-dpf-97}
triangulates polygon $A$, dissects each triangle to a rectangle,
converts each rectangle to one of fixed length, and stacks all the rectangles.
Applying the same process to $B$ and overlaying the stacked rectangles yields
a mutual dissection.
No comparable method is known for hinged dissections:

\begin{center}
\fbox{
\begin{minipage}[h]{0.75\linewidth}
{\sc question:} Does every pair of equal-area polygons have
a hinged dissection?
\end{minipage}
}
\end{center}

\noindent
The usual interpretation of this problem ignores possible intersections between
the pieces as they hinge, 
following what Frederickson calls the ``wobbly-hinged'' model.  
%p15
%(This appears not to be a true restriction, as a finer dissection
%should permit avoiding potential collisions.)
Removing this freedom is perhaps not difficult, but seems not to
be settled in the literature.

Here I report on two advances on this problem.
The first is a proof that any two \emph{polyominoes} of the same area
have a hinged dissection~\cite{ddeff-hdpp-03}.
A polyomino is a polygon formed by joining unit squares at their
edges~\cite{g-p-65,k-p-97}. One composed of $n$ squares is called an \emph{$n$-omino}.
The authors establish a type of universal dissection by proving that
a cycle of $2n$ right isosceles triangles, hinged at their base vertices,
can fold to any $n$-omino.
See Fig.~\figref{polyomino}.
Although the cycle may seem a special case, they prove that any hinged
graph structure may be converted into another dissection hinged
in a cycle.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure Begin
\begin{figure}[htbp]
\centering
\includegraphics[width=\linewidth]{polyomino.eps}
%\fbox{polyomino.eps}
\caption{Eight right isosceles triangles hinging to a tetramino.}
\figlab{polyomino}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure End
The polyomino result generalizes to hinged dissections 
of all edge-to-corresponding-edge gluings
of congruent copies of any polygon.
This leads, among other curiosities, 
to a $128$-piece hinged chain of isosceles right triangles
that folds to shapes representing
all the letters of the
alphabet and the ten digits~\cite{HingedAlphabet}.

The second advance is a proof by Eppstein~\cite{e-hkmd-01} that
any asymmetric polygon has a hinged dissection to its mirror image.
His dissection partitions the polygon into a chain of \emph{kites},
quadrilaterals with reflection symmetry across a diagonal.
With this partition in hand, it is easy to rotate the kites so all
their symmetry diagonals align.  The mirror image of
the unfolding process then folds the shape to its mirror image.
This procedure is illustrated for a simple example in Fig.~\figref{kites}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure Begin
\begin{figure}[htbp]
\centering
\includegraphics[width=\linewidth]{kites.eps}
%\fbox{kites.eps}
\caption{A dissection into a chain of kites,
hinging to the mirror image.  Here the kites are all squares.}
\figlab{kites}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure End
The kite partition relies on circle packing~\cite{BerEpp-IJCGA-00},
and must be supplemented by a refined partition, and threading
around the boundary of a spanning tree to obtain a hinged chain.
This work leads to a possible route toward solving
the general problem for hinged dissections, for it reduces
it to $O(n)$ equal-area triangle hinge-dissection problems with particular constraints
on the hinges.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\small
\bibliographystyle{/home1/orourke/tex/alphasort}
\bibliography{44,/home1/orourke/bib/geom/geom}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}


\begin{enumerate}
\end{enumerate}

%10lines
see Fig.~\figref{X}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure Begin
\begin{figure}[htbp]
\centering
\includegraphics[width=\linewidth]{X.eps}
%\fbox{X.eps}
\caption{Z.}
\figlab{X}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure End

mac.tex
\newenvironment{pf}{\unskip{\bf Proof:}}{\unskip{\hfill $\Box$}}
\def\noproof{\unskip{\hfill $\Box$}}
\newcommand{\lemlab}[1]{\label{lemma:#1}}
\newcommand{\theolab}[1]{\label{theo:#1}}
\newcommand{\codelab}[1]{\label{code:#1}}
\newcommand{\alglab}[1]{\label{alg:#1}}
\newcommand{\eqlab}[1]{\label{eq:#1}}
\newcommand{\corlab}[1]{\label{cor:#1}}
\newcommand{\deflab}[1]{\label{def:#1}}
\newcommand{\factlab}[1]{\label{fact:#1}}
\newcommand{\tablab}[1]{\label{tab:#1}}
\newcommand{\figlab}[1]{\label{fig:#1}}
\newcommand{\seclab}[1]{\label{section:#1}}
\newcommand{\chaplab}[1]{\label{chapter:#1}}
\newcommand{\lemref}[1]{\ref{lemma:#1}}
\newcommand{\coderef}[1]{\ref{code:#1}}
\newcommand{\theoref}[1]{\ref{theo:#1}}
\newcommand{\algref}[1]{\ref{alg:#1}}
\newcommand{\corref}[1]{\ref{cor:#1}}
\newcommand{\defref}[1]{\ref{def:#1}}
\newcommand{\factref}[1]{\ref{fact:#1}}
\newcommand{\tabref}[1]{\ref{tab:#1}}
\newcommand{\figref}[1]{\ref{fig:#1}}
\newcommand{\secref}[1]{\ref{section:#1}}
\newcommand{\chapref}[1]{\ref{chapter:#1}}
\newcounter{listcounter}
\newcommand{\li}{\item}
\newtheorem{theorem}{Theorem}[section]
%\newtheorem{lemma}{Lemma}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{conj}{Conjecture}[section]
%\newtheorem{conj}{Conjecture}
\newtheorem{df}{Definition}[section]
%\newtheorem{df}{Definition}
\newtheorem{fact}{Fact}[section]
%
%INITIALIZED VALUES
%
\newcounter{mycounter}
%
{\catcode`\@=11
\gdef\setft#1#2#3{%
\def\@oddfoot{
{\setbox0=\hbox{#1}
\setbox1=\hbox{#3}
\ifdim\wd0>\wd1
\dimen0=\wd0
\box0\hfil#2\hfil\hbox to\dimen0{\hfil\hfil\box1}
\else \dimen0=\wd1
\hbox to\dimen0{\box0\hfil }\hfil#2\hfil\box1 \fi
}}} }

  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  %%  Some code to insert marginal comments and number them in a paper.	%%
  %%  By default marginal comments are ignored.  If the command		%%
  %%  \withcomplaints is called, complaints are numbered, the number	%%
  %%  between dashes appears on the tex raised in a 0 width box so it	%%
  %%  does not affect the layout.					%%
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\complaint#1{}
\def\withcomplaints{
%\addtolength{\oddsidemargin}{-1.4cm}
%\addtolength{\evensidemargin}{-1.4cm}
\newcounter{mycomplaints}
\def\complaint##1{\refstepcounter{mycomplaints}%
\ifhmode%
\unskip%
{\dimen1=\baselineskip \divide\dimen1 by 2 %
\raise\dimen1\llap{\tiny -\themycomplaints-}}\fi%
\marginpar{\tiny [\themycomplaints]: ##1}}%
}


44.bbl
\newcommand{\etalchar}[1]{$^{#1}$}
\begin{thebibliography}{DDE{\etalchar{+}}03}

\bibitem[BE00]{BerEpp-IJCGA-00}
Marshall~W. Bern and David Eppstein.
\newblock Quadrilateral meshing by circle packing.
\newblock {\em Int. J. Computational Geometry {\&} Applications},
  10(4):347--360, August 2000.

\bibitem[DD03]{HingedAlphabet}
Erik~D. Demaine and Martin~L. Demaine.
\newblock Hinged dissection of the alphabet.
\newblock {\em Journal of Recreational Mathematics}, 31(3):204--207, 2003.

\bibitem[DDE{\etalchar{+}}03]{ddeff-hdpp-03}
Erik~D. Demaine, Martin~L. Demaine, David Eppstein, Greg~N. Frederickson, and
  Erich Friedman.
\newblock Hinged dissection of polyominoes and polyforms.
\newblock {\em Computational Geometry: Theory and Applications}, 2003.
\newblock To appear. arXiv:cs.CG/9907018. Revised version of paper in {\em
  Proc. 11th Canad. Conf. Comput. Geom.}, 1999, 15--18.

\bibitem[Epp01]{e-hkmd-01}
David Eppstein.
\newblock Hinged kite mirror dissection.
\newblock ACM Computing Research Repository, June 2001.
\newblock {arXiv:cs.CG/0106032}.

\bibitem[Fre97]{f-dpf-97}
Greg Frederickson.
\newblock {\em Dissections: Plane and Fancy}.
\newblock Cambridge University Press, 1997.

\bibitem[Fre02]{f-hdst-02}
Greg Frederickson.
\newblock {\em Hinged Dissections: Swinging \& Twisting}.
\newblock Cambridge University Press, 2002.

\bibitem[Gol65]{g-p-65}
Solomon~W. Golomb.
\newblock {\em Polyominoes}.
\newblock Charles Scribner's Sons, New York, 1965.

\bibitem[Kla97]{k-p-97}
David~A. Klarner.
\newblock Polyominoes.
\newblock In Jacob~E. Goodman and Joseph O'Rourke, editors, {\em Handbook of
  Discrete and Computational Geometry}, chapter~12, pages 225--242. CRC Press
  LLC, Boca Raton, FL, 1997.

\end{thebibliography}
