\pdfoutput=1 %arXiv addition for pdflatex, permits no file extensions.
%Must go on first line!
\documentclass[letterpaper]{cccg10}
\usepackage{url,float}
\usepackage{graphicx}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{latexsym}
%\input{/home/orourke/tex/mac}
%\withcomplaints
\newcommand{\hide}[1]{}
%\newcommand{\ABox}{
%\raisebox{3pt}{\framebox[6pt]{\rule{6pt}{0pt}}}
%}
%\newenvironment{proof}{{\bf Proof:}}{\hfill\ABox}
%\newenvironment{pf}{{\bf Proof:}}{\hfill\ABox}
%\newtheorem{theorem}{{\bf Theorem}}
\newtheorem{corollary}[theorem]{Corollary}
%\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{conjecture}[theorem]{Conjecture}
%\newtheorem{definition}[theorem]{Definition}
%For labels of items.
\newcommand{\lemlab}[1]{\label{lemma:#1}}
\newcommand{\thmlab}[1]{\label{thm:#1}}
\newcommand{\eqlab}[1]{\label{eq:#1}}
\newcommand{\corlab}[1]{\label{cor:#1}}
\newcommand{\deflab}[1]{\label{def:#1}}
\newcommand{\tablab}[1]{\label{tab:#1}}
\newcommand{\figlab}[1]{\label{fig:#1}}
\newcommand{\seclab}[1]{\label{sec:#1}}
\newcommand{\chaplab}[1]{\label{chap:#1}}
\newcommand{\lemref}[1]{\ref{lemma:#1}}
\newcommand{\thmref}[1]{\ref{thm:#1}}
\newcommand{\corref}[1]{\ref{cor:#1}}
\newcommand{\defref}[1]{\ref{def:#1}}
\newcommand{\chapref}[1]{\ref{chap:#1}}
\newcommand{\secref}[1]{\ref{sec:#1}}
\newcommand{\eqref}[1]{\ref{eq:#1}}
\newcommand{\figref}[1]{\ref{fig:#1}}
\newcommand{\tabref}[1]{\ref{tab:#1}}
%\floatstyle{ruled}
%\newfloat{algorithm}{htbp}{loa}
%\floatname{algorithm}{Algorithm}
%From Erik Demaine:
% Complex \xxx for making notes of things to do. Use \xxx{...} for general
% notes, and \xxx[who]{...} if you want to blame someone in particular.
% Puts text in brackets and in bold font, and normally adds a marginpar
% with the text `xxx'' so that it is easy to find. On the other hand, if
% the comment is in a minipage, figure, or caption, the xxx goes in the text,
% because marginpars are not possible in these situations.
{\makeatletter
\gdef\xxxmark{%
\expandafter\ifx\csname @mpargs\endcsname\relax % in minipage?
\expandafter\ifx\csname @captype\endcsname\relax % in figure/caption?
\marginpar{xxx}% not in a caption or minipage, can use marginpar
\else
xxx % notice trailing space
\fi
\else
xxx % notice trailing space
\fi}
\gdef\xxx{\@ifnextchar[\xxx@lab\xxx@nolab}
\long\gdef\xxx@lab[#1]#2{{\bf [\xxxmark #2 ---{\sc #1}]}}
\long\gdef\xxx@nolab#1{{\bf [\xxxmark #1]}}
% This turns them off:
%\long\gdef\xxx@lab[#1]#2{}\long\gdef\xxx@nolab#1{}%
\gdef\turnoffxxx{\long\gdef\xxx@lab[##1]##2{}\long\gdef\xxx@nolab##1{}}%
}
% Blackboard R for real numbers, S for sphere (\S taken someplace, so \Sph).
\def\P{{\mathcal P}}
\def\Q{{\mathcal Q}}
\def\G{{\Gamma}}
\def\g{{\gamma}}
\def\l{{\lambda}}
\def\r{{\rho}}
\def\s{{\sigma}}
\def\d{{\delta}}
\def\a{{\alpha}}
\def\b{{\beta}}
%\def\C{{\mathcal C}}
%\def\hull{\mathop{\rm hull}\nolimits}
\def\sp{\mathop{\rm sp}\nolimits}
\newcommand{\squeezelist}{\setlength{\itemsep}{0pt}}
%\newcounter{abc}
\title{Sweeping Minimum Perimeter Enclosing Parallelograms:\\
Optimal Crumb Cleanup}
%\\\emph{Draft}}
\author{%
Yonit Bousany%
\thanks{\protect\url{ybousany@smith.edu}.}
\and
Mary Leah Karker%
\thanks{\protect\url{mkarker@smith.edu}.}
\and
Joseph O'Rourke%
\thanks{Dept. of Computer Science, Smith College, Northampton, MA
01063, USA.
\protect\url{orourke@cs.smith.edu}.}
\and
Leona Sparaco%
\thanks{\protect\url{lparaco@smith.edu}.}
}%author
\begin{document}
\maketitle
\begin{abstract}
We characterize the optimal 2-sweeps of triangles, and provide a
linear-time algorithm for convex polygons.
\end{abstract}
\section{Introduction}
A fascinating problem was introduced by Dumitrescu and Jiang in~\cite{dj-sp-09}:\footnote{
They credit
%Pawe\l
Pawel
\.{Z}yli\'{n}ski
as the originator.
}
What is the optimal way to sweep points in the plane all to one target
point?
In their model, the sweeper is an infinite line that moves orthogonal
and parallel to itself, pushing points along the sweep direction.
The cost of a sweep is the distance swept
(with no cost for how many points are pushed at once, as in the ``earth mover's distance'').
The cost of multiple sweeps is the sum of each individual sweep's cost, with
no cost assessed for repositioning in preparation for the next sweep.
The problem is to sweep all the points into one point, selected by the
algorithm.
The sweep line may be viewed as a ``table crumber'' or ``crumb
scraper,'' the instrument
waiters use in restaurants to clean the table cloth between courses.
In~\cite{dj-sp-09}, several variants of the problem are considered,
most involving sweeping a discrete set of points.
Here we explore another natural variant.
In our model the crumbs form a continuous simply connected region of
the plane, for example, a simple polygon.
We use a different sweep model, where the infinite sweep line $L$ may
translate
by any vector $v$, not only by vectors orthogonal to $L$ as
in~\cite{dj-sp-09}.
Each point swept moves by $v$, with the sweep cost $|v|$. This model is appropriate if the
crumbs
have sufficent friction to avoid sliding along the sweeper.
Our goal is to find the optimal sweep strategy and its cost for a
given shape.
Our contributions are as follows:
\begin{enumerate}
\squeezelist
\item We show that sometimes more than two sweeps are needed to
optimally sweep nonconvex shapes, but we conjecture that two sweeps
always suffice for convex shapes.
\item Restricting attention two sweeps, the best two sweeps are
determined by the minimum perimeter enclosing parallelogram.
\item We characterize the optimal two sweeps for triangles.
\item We provide a linear-time algorithm for finding the
minimum perimeter enclosing parallelogram
(and so the optimal two sweeps) for any convex $n$-gon.
\end{enumerate}
\section{Multiple Sweeps}
\begin{lemma}[1-Sweep]
One sweep suffices if and only if all the points swept are collinear,
in which case the cost is the length of the shortest segment containing
all the points.
\lemlab{1-sweep}
\end{lemma}
\begin{proof}
All points swept move parallel to the sweep, and so can only end up at
one target point if they lie along a line.
\end{proof}
\begin{lemma}[2-Sweeps]
The optimal 2-sweep strategy for any shape $S$ is to sweep parallel to the edges of the
minimum
perimeter parallelogram enlosing $S$, with cost half the perimeter.
\lemlab{2-sweeps}
\end{lemma}
\begin{proof}
By Lemma~\lemref{1-sweep}, the first sweep must push $S$ to a line
segment.
Two sweeps then determine a parallelogram, and the cost is the sum of
the lengths of two consecutive edges.
\end{proof}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure Begin
\begin{figure}[htbp]
\centering
\includegraphics[width=\linewidth]{Figures/EqTri24}
\caption{Two ways to sweep an equilateral triangle.}
\figlab{EqTri24}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure End
\paragraph{Example.}
Figure~\figref{EqTri24} shows two ways to sweep a unit equilateral
triangle.
In~(a) two sweeps are used: down the $\sqrt{3}/2$ altitude, and then
left across the base.
In~(b) four sweeps are used, the first two using
$1/(2\sqrt{3})$ and $1/\sqrt{3}$ to
produce a $\frac{1}{3}$
by $\frac{2}{3}$, which is then reduced to a point with two more
sweeps.
The total cost for both strategies is $1+\sqrt{3}/2$.
Indeed, we have found many distinct strategies for this shape
(including infinite series of sweeps)
that all
result
in the same cost, which we conjecture to be optimal.
An argument in~\cite{dj-sp-09} gives a lower bound of $\sqrt{3}$,
smaller by $\approx 0.13$.
\paragraph{Nonconvex Shapes.}
Figure~\figref{NonConvex3} shows a simple example where three sweeps
are superior to two sweeps.
The 3-sweeps illustrated cost $\sqrt{2}+2 \approx 3.41$ but the 2-sweep cost (using
Lemma~\lemref{2-sweeps} and Lemma~\lemref{1-flush} below)
is $\sqrt{5}+1\frac{1}{2} \approx 3.73$.
Henceforth we study two sweeps:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure Begin
\begin{figure}[htbp]
\centering
\includegraphics[width=0.75\linewidth]{Figures/NonConvex3}
\caption{Three sweeps can be better than two.}
\figlab{NonConvex3}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure End
\begin{conjecture}
The optimal cost of sweeping any convex shape $S$ can be achieved by
two sweeps.
\end{conjecture}
\section{One Flush, Two Flush}
Restricting attention to two sweeps reduces the problem via
Lemma~\lemref{2-sweeps}
to finding a minimum perimeter enclosing parallelogram.
Lemma~1 in~\cite{mp-mpe-08} implies this:
\begin{lemma}[1-Flush]
A minimum perimeter parallelogram enclosing a polygon $Q$ has one edge flush with
the
convex hull of $Q$.
\lemlab{1-flush}
\end{lemma}
They prove a somewhat different (and more general) result, but when
specialized to parallelograms, the above is implied by their proof.
We now further restrict attention to triangles. Obviously for
triangles, either just one edge is flush, or two edges are flush.
We characterize precisely the conditions separating these two cases:
\begin{theorem}
Let $T$ be a triangle, and $P$ its minimum perimeter enclosing parallelogram.
If $T$ is obtuse, $P$ is flush with the two edges forming the obtuse
angle.
If $T$ is acute, $P$ is a rectangle flush with the shortest edge.
\thmlab{triangles}
\end{theorem}
Normalize the triangle $T$ so that its longest side has length $1$;
let the other two sides have lengths $a \le b \le 1$.
We can then view the space of all triangles as points $(a,b)$.
Figure~\figref{FlushGraph} illustrates the import of the theorem.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure Begin
\begin{figure}[htbp]
\centering
\includegraphics[width=0.75\linewidth]{Figures/FlushGraph}
\caption{Theorem~\protect\thmref{triangles} in the $(a,b)$ space.}
\figlab{FlushGraph}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure End
We must have $a+b \ge 1$ to satisfy the triangle inequality.
Let $\theta$ be the angle at the $ab$-vertex.
All points along the circular arc have $\theta=90^\circ$, those
below are obtuse, those above, acute.
The triple point $(a,b)=(\frac{\sqrt{2}}{2},\frac{\sqrt{2}}{2})$ represents the
triangle where 1-flush against $a$ is also 1-flush against $b$
and so is 2-flush against $a$ and $b$.
\begin{proof}
% Normalize the triangle $T$ so that its longest side has length $1$;
% let the other two sides have lengths $a \le b \le 1$.
% Let $\theta$ be the angle at the $ab$-vertex.
Observe that $a+b \le a+1 \le b+1$.
Therefore 2-flush against the two shorter sides always beats the other
possible 2-flush cases.
We analyze the competing cases illustrated in
Figures~\figref{TrianglesSixAcute} and~\figref{TrianglesSixObtuse}.
That the 1-flush rectangles illustrated are the appropriate cases to
consider is not justified until Corollary~\corref{projection}.
\paragraph{$\theta$ Acute.}
%see Figure~\figref{TrianglesSixAcute}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure Begin
\begin{figure}[htbp]
\centering
\includegraphics[width=\linewidth]{Figures/TrianglesSixAcute}
\caption{$\theta$ Acute: 1-flush against the shortest side wins.}
\figlab{TrianglesSixAcute}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure End
Denote by $h_a$ the height of the parallelogram that is flush against the
shortest side $a$. See Figure~\figref{TrianglesSixAcute}.
\begin{description}
\item[Claim 1:] 1-flush against shortest side beats all 2-flush cases
(bottom row of Figure~\figref{TrianglesSixAcute}).
%\textsl{Proof} :
Because we have a right triangle, $h_a < b$. Thus $h_a+a < a+b$.
So 1-flush against $a$ beats 2-flush against $a$ and $b$ and hence beats all 2-flush cases.
\item[Claim 2:] 1-flush against shortest side beats 1-flush against longest side.
%\textsl{Proof} :
Let $h_1$ be the height of the parallelogram flush against the longest
side. Because we have a right triangle, $h_a < 1$. Therefore :
\begin{eqnarray*}
h_a(1-a) & < & (1-a)\\
h_a-h_aa & < & 1-a\\
h_a+a & < & 1+h_a+a
\end{eqnarray*}
From our area equations $1/2 \cdot 1 \cdot h_1$ = $1/2 \cdot h_aa$,
therefore $h = h_aa$.
Thus $h_a+a < 1+h$.\\
\item[Claim 3:] 1-flush against shortest side $a$ beats 1-flush
against median-length side $b$.
%\textsl{Proof} :
Define $h_b$ as the height of the parallelogram flush against side
$b$. Since $a < b$, it follows that
\begin{eqnarray*}
a(1 - h_a/b) & < & b(1 - h_a/b)\\
a - ah_a/b & < & b - bh_a/b
\; < \; b + ah_a/b
\end{eqnarray*}
%$a(1 - h_a/b) < b(1 - h_a/b)$ and
%$a - ah_a/b < b - bh_a/b < b + ah_a/b$.
Expressing the area of the triangle two ways yields
$\frac{1}{2} ah_a =\frac{1}{2} bh_b$,
and hence $ah_a/b = h_b$.
Thus $a+h_a < b+h_b$.
\end{description}
Therefore 1-flush against the shortest side $a$ wins in all cases.
\paragraph{$\theta$ Obtuse.}
%see Figure~\figref{TrianglesSixObtuse}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure Begin
\begin{figure}[htbp]
\centering
\includegraphics[width=\linewidth]{Figures/TrianglesSixObtuse}
\caption{$\theta$ Obtuse: 2-flush against the shorter sides win.}
\figlab{TrianglesSixObtuse}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure End
\begin{description}
\item[Claim 1:] 2-flush against shortest sides beats 1-flush against
shortest side $a$.
Extend side $a$ by length $x$ so that a perpendicular line of length
$h_a$ intersects the $b, 1$ vertex (we have created a right triangle
with sides $x, h_a, b$). The cost of sweeping 1-flush against $a$ will
be $a+x+h_a$. By the triangle inequality, $b < h_a+x$. Thus $a+b <
a+x+h_a$.
\item[Claim 2:] 2-flush against shortest sides beats 1-flush against
the median-length
side $b$.
Extend side $b$ by length $y$ so that a perpendicular line of length $h_b$ intersects the $a, 1$ vertex (we have created a right triangle with sides $y, h_b, a$). The cost of sweeping 1-flush against $b$ will be $b+y+h_b$. By the triangle inequality, $a < h_b+y$. Thus $a+b < h_b+y+b$.
\item[Claim 3:] 2-flush against shortest sides beats 1-flush against
the longest side.
This is the only case for which we have no succinct proof.
In terms of the viewpoint of Figure~\figref{FlushGraph},
we computed the locus of $(a,b)$-points representing triangles
where the 2-flush and 1-flush instances being compared
have identical perimeter. This locus is a curve $\Gamma$, which
is explicitly:
$$
b(a) = \frac{1}{3} \left(\frac{2 \sqrt[3]{2}
\left(a^2+a-2\right)}{D}+a+2^{2/3} D-1\right) , D=
$$
$$
\sqrt[3]{-2 a^3-3 a^2+3 \sqrt{3} \sqrt{(a-1)^2 \left(3 a^2+8
a+16\right)}-15 a+20}
$$
Now the transition between obtuse and acute $\theta$ is the quarter
circle
arc. As
Figure~\figref{HardCase} shows, the latter falls inside $\Gamma$.
Thus, for all obtuse $\theta$, the 2-flush perimeter is smaller.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure Begin
\begin{figure}[htbp]
\centering
\includegraphics[width=0.75\linewidth]{Figures/HardCase}
\caption{Points on $\Gamma=b(a)$ represent acute $\theta$.}
\figlab{HardCase}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure End
For example, 1-flush for isosceles triangles does not start to beat
2-flush until $\theta \le 2 \cos^{-1}\frac{4}{5} \approx 74^\circ$.
The reason $\Gamma$ does not show up in Figure~\figref{FlushGraph}
is that the 1-flush cases against the shortest side dominate.
\end{description}
\end{proof}
\begin{corollary}
The minimum perimeter parallelogram
enclosing a random triangle is twice as likely to have two sides
flush than it is to have just one side flush.
\end{corollary}
\begin{proof}
In the model that selects the three triangle vertices uniformly and
randomly on a circle,
it is well known that the probability of an obtuse angle is
$\frac{3}{4}$.
\end{proof}
\section{Algorithm for Convex Polygons}
With the 1-flush lemma (Lemma~\lemref{1-flush}) in hand, an outline of
an algorithm to find the best parallelogram $P$ enclosing a convex $n$-gon $C$
is easy:
\textbf{for} each edge $e$ of $C$ selected as being flush with $P$,
find the optimal orientation of the other side of $P$.
We will show how this best second side orientation can be found in
$O(n)$ time, then in $O(\log n)$ time, and finally in $O(1)$ amortized
time,
leading to successively faster algorithms, culminating in a
linear-time algorithm.
First we consider a situation with the 1-flush side of $P$ fixed as
horizontal,
and the free side of $P$ pivoting on two points, ignoring the actual
shape
of $C$ between the pivots, as illustrated in
Figure~\figref{Pivots}(a).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure Begin
\begin{figure}[htbp]
\centering
\includegraphics[width=\linewidth]{Figures/Pivots}
\caption{The minimum perimeter parallelogram is achieved with
$\theta= \cos^{-1} (0.2) \approx 78^\circ$.}
\figlab{Pivots}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure End
The minimum perimeter parallelogram is determined solely as a function
of the vertical separation of the pivots:
\begin{lemma}
Let $\Delta y$ be the vertical separation of the pivots when the
height of the parallelogram is normalized to 1. Then the perimeter
$\rho(\theta)$
of $P$ has a unique minimum at the value $\theta^*= \cos^{-1} (\Delta y)$.
\lemlab{arccos}
\end{lemma}
\begin{proof}
Letting the heights of the two pivots be $y_1$ and $y_1+\Delta y$,
$\rho(\theta)$
can be expressed as a function of $\{ y_1, \Delta y, \Delta x, \theta
\}$.
The derivative of $\rho(\theta)$ solves explictly to the claimed
expression.
\end{proof}
\noindent
The lemma is illustrated in Figure~\figref{Pivots}(b).
We have not yet found a geometric proof of the lemma.
Now imagine rotating ``calipers'' around the convex polygon $C$,
with angle varying from $\theta=0$ with respect to the $x$-axis and
flush edge, to $\theta=180^\circ$.
The left pivot walks down the left side of $C$ while the right pivot
walks up the right side of $C$.
For each $\theta$, the pair of pivots determine a $\Delta y$ value
(left minus right vertical height),
which
determines the optimal angle $\theta^*$ via Lemma~\lemref{arccos}.
But for many pivots, the line at this angle is not tangent to $C$, but
rather
penetrates $C$.
Figure~\figref{PivotsArcCos} illustrates this on the left side.
When the $\theta^*$ value penetrates $C$ at either pivot, it means
that the caliper tangents determining those pivots do not determine
a minimum perimeter parallelogram: we are on the downslope in
Figure~\figref{Pivots}(b)
and the perimeter can be decreased by moving to another pivot.
When the $\theta^*$ lines are also tangent to $C$ at both
pivots, we are at the unique local minimum of the perimeter.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure Begin
\begin{figure}[htbp]
\centering
\includegraphics[width=0.9\linewidth]{Figures/PivotsArcCos}
\caption{Tangent lines at angle $\theta$ determine pivots, and
pivots determine $\theta^*$ values.
%$106^\circ$, $94^\circ$, $84^\circ$, and $67^\circ$.
Here it is only the
last
$\theta^*=67^\circ$ that is also tangent to the determining pivot.}
\figlab{PivotsArcCos}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure End
A second circumstance that determines the minimum perimeter is when
$\theta^*$ penetrates $C$ below at one pivot and penetrates $C$ above
at the
next pivot, in which case the minimum is determined by the angle of
the edge between.
Now $\Delta y$ is a monotonically increasing step function of the caliper angle $\theta$, as
shown in
see Figure~\figref{StaircaseGraphs}(a),
and so $\cos^{-1} (\Delta y)$ is a monotically decreasing step
function~(b).
We seek an angle $\theta^*$ that satisfies $\theta^* = \cos^{-1}
[\Delta y (\theta^*)]$, for such a $\theta^*$ is both a minimum by
Lemma~\lemref{arccos}
and tangent to the pivots.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure Begin
\begin{figure}[htbp]
\centering
\includegraphics[width=\linewidth]{Figures/StaircaseGraphs}
\caption{Graphs of $\Delta y$ and $\cos^{-1} (\Delta y)$ for
Figure~\protect\figref{PivotsArcCos} .}
\figlab{StaircaseGraphs}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure End
In Figure~\figref{StaircaseGraphs}(b) this is depicted by intersecting
the $\cos^{-1}(\theta)$ staircase with the diagonal line $\theta^*=\theta$.
When that diagonal pierces the staircase on a horizontal step (as
illustrated),
then the minimum is achieved rocking on both pivots;
when the diagonal pierces a vertical step, the minimum is achieved with
the corresponding edge flush.
This analysis establishes two facts:
\begin{lemma}
With one edge of $P$ fixed flush with an edge of $C$, the minimum
perimeter parallelogram is unique, and can be found in $O(\log n)$
time
by binary search for the intersection point in
Figure~\figref{StaircaseGraphs}(b).
\lemlab{unique}
\end{lemma}
\noindent
We will not justify this further because we only use the uniqueness.
A consequence of the preceding two lemmas is this:
\begin{corollary}
If a convex polygon $C$ has one edge $e$ such that all other edges of
$C$ project orthogonally into $e$, then the
minimum perimeter enclosing parallelogram with one side flush with $e$
is the enclosing rectangle with base $e$.
\corlab{projection}
\end{corollary}
\begin{proof}
When the pivot points are the two endpoints of $e$---which they can be
because of the projection assumption---then $\Delta y=0$
and by Lemma~\lemref{arccos}, $\theta^*=90^\circ$.
By Lemma~\lemref{unique} this is the unique minimum.
\end{proof}
\paragraph{Optimal Pivots.}
The following lemma shows that the search for $P$ based on
edge $e$ of $C$ chosen to satisfy the 1-Flush lemma need not start
anew for the next edge $e'$ of $C$:
\begin{lemma}
Let $p$ and $q$ be the left and right side pivots for the minimum perimeter
parallelogram $P$
with base edge flush with edge $e$ of $C$.
Then the left and right pivots $p'$ and $q'$ for
the optimal parallelogram $P'$ flush with the next edge $e'$
counterclockwise of $e$ on $C$, are either the same as $p$ and $q$ or
counterclockwise
of $p$ and $q$.
\lemlab{pivots}
\end{lemma}
\begin{proof}
% Let $\theta^*$ be the angle between the base and left side of $P$.
% The line containing this left side makes a larger angle $\theta^{*}' > \theta^*$ with
% the line containing $e'$.
The value of $\Delta y$ decreases to $\Delta y' < \Delta y$ for the
same pivots $p$ and $q$ with respect to the new base line containing
$e'$.
With $\Delta y'$ smaller, ${\theta^*}' = \cos^{-1} \Delta y'$ is larger;
see Figure~\figref{StaircaseGraphs}.
Not only is ${\theta^*}' > \theta^*$, it is larger with respect to a base
line
that has rotated counterclockwise from the base line from which
$\theta^*$ is measured. Consequently, the side of $P'$ realizing
${\theta^*}'$ is rotated counterclockwise of the line of $P$ realizing $\theta$.
\end{proof}
This leads to a linear-time algorithm.
First find the optimal $P$ for any start edge $e_0$ of $C$ as the one flush,
in $O(n)$ time.
Then,
\textbf{for} each successive counterclockwise edge $e$ of $C$,
fix that as the one flush, and search for the optimal pivots
counterclockwise of the previous pivots.
Lemma~\lemref{pivots} guarantees this will find the best
parallelogram.
Examples are shown in
Figure~\figref{Decagons}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure Begin
\begin{figure}[htbp]
\centering
\includegraphics[width=\linewidth]{Figures/Decagons}
\caption{Minimum perimeter parallelogram in red.
(a)~1-flush minimum. (b)~2-flush minimum.}
\figlab{Decagons}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure End
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\small
%\baselineskip=0.9\baselineskip
% Decrease the space between bibliography items.
%\let\realbibitem=\bibitem
%\def\bibitem{\par \vspace{-0.6ex}\realbibitem}
%\bibliographystyle{alpha}
%\bibliographystyle{plain}
%\bibliography{/Users/orourke/bib/geom/geom}
\begin{thebibliography}{MP08}
\bibitem[DJ09]{dj-sp-09}
Adrian Dumitrescu and Minghui Jiang.
\newblock Sweeping points.
\newblock {\em Algorithmica}, 2009.
\newblock To appear, 2010.
\bibitem[MP08]{mp-mpe-08}
Joseph~S.B. Mitchell and Valentin Polishchuk.
\newblock Minimum-perimeter enclosures.
\newblock {\em Information Processing Letters}, 107(3--4):120--124, 2008.
\end{thebibliography}
\end{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
see Figure~\figref{X}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure Begin
\begin{figure}[htbp]
\centering
\includegraphics[width=0.75\linewidth]{Figures/X}
\caption{Y.}
\figlab{X}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure End