Unfolding Orthogonal Polyhedra with Quadratic Refinement:\\ The Delta-Unfolding Algorithm
Mirela Damian% \thanks{Dept. of Computing Sciences
Villanova
PA 19085
Erik D. Demaine% \thanks{Computer Science and Artificial Intelligence Laboratory
32 Vassar St.
Cambridge
MA 02139
Robin Flatland% \thanks{Dept. of Computer Science
Siena College
Loudonville
NY 12211
We show that every orthogonal polyhedron homeomorphic to a sphere can be unfolded without overlap while using only polynomially many (orthogonal) cuts. By contrast, the best previous such result used exponentially many cuts. More precisely, given an orthogonal polyhedron with $n$ vertices, the algorithm cuts the polyhedron only where it is met by the grid of coordinate planes passing through the vertices, together with $\Theta(n^2)$ additional coordinate planes between every two such grid planes.
DeltaUnf.tex
\pdfoutput = 1
\documentclass[11pt]{article}
\usepackage{url}
\usepackage{graphicx}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{latexsym}
\usepackage{color}
\usepackage{enumerate}
\usepackage{hyperref}

\topmargin 0in              % LaTeX adds an inch=25.4mm
\headheight 0pt                 % no headers
\headsep 0in                    % no headers
\textheight 9in              % i.e., bottom margin = 1in

\textwidth 6.5in
\oddsidemargin 0in              % (8.5-textwidth)/2 = 1in
                                % LaTeX adds an inch

\newcommand{\notyet}[1]{}
\newcommand{\squeezelist}{\setlength{\itemsep}{0pt}}
\newcommand\R{\mathbb{R}}
\newcommand\red[1]{\textcolor{red}{#1}}
\newcommand\blue[1]{\textcolor{blue}{#1}}


%-------------------------------------------------------------------
%Commands to have one document produce both the conf and full versions:
%\full{text} is only in full; \conf{text} is only in conf; all else in
%both.
%The {} version makes it disappear; the {#1} version makes it appear.
%Use the two outside lines (1st & 4th) for conf,
%the two inside (2nd & 3rd) for full.
%%\newcommand{\full}[1]{}
%\newcommand{\full}[1]{#1} %Uncomment this line for full

%\newcommand{\conf}[1]{}   %Uncomment this line for full
%%\newcommand{\conf}[1]{#1}
%-------------------------------------------------------------------

\newcommand{\ABox}{
\raisebox{3pt}{\framebox[6pt]{\rule{6pt}{0pt}}}
}
\newenvironment{proof}{{\bf Proof:}}{\hfill\ABox}

\newtheorem{theorem}{{\bf Theorem}}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{openquestion}[theorem]{Open question}

%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\bP{{\partial P}}
\def\bI{{\partial I}}
\def\bU{{\partial U}}
%\newcommand\Sph{\mathbb{S}}

%\def\nothing{\circ}
\def\nothing{\ast}

\begin{document}

\title{Unfolding Orthogonal Polyhedra with Quadratic Refinement:\\
The Delta-Unfolding Algorithm}
\author{Mirela Damian%
   \thanks{Dept. of Computing Sciences, Villanova University, Villanova,
    PA 19085, USA.
   \protect\url{mirela.damian@villanova.edu}.}
\and
Erik D. Demaine%
     \thanks{Computer Science and Artificial Intelligence Laboratory,
       Massachusetts Institute of Technology,
       32 Vassar St., Cambridge, MA 02139, USA. \protect\url{edemaine@mit.edu}.
       Partially supported by NSF CAREER award CCF-0347776.}
\and
Robin Flatland%
   \thanks{Dept. of Computer Science, Siena College, Loudonville, NY 12211, USA.
    \protect\url{flatland@siena.edu}.}
}

\date{}
\maketitle

\begin{abstract}
  We show that every orthogonal polyhedron homeomorphic to a sphere can be
  unfolded without overlap while using only polynomially many (orthogonal) cuts.
  By contrast, the best previous such result used exponentially many cuts.
  More precisely, given an orthogonal polyhedron with $n$ vertices,
  the algorithm cuts the polyhedron only where it is met by
  the grid of coordinate planes passing through the vertices,
  together with $\Theta(n^2)$ additional coordinate planes
  between every two such grid planes.
\end{abstract}

\section{Introduction}

One of the major unsolved problems in geometric folding is whether every
polyhedron (homeomorphic to a sphere) has an ``unfolding''
\cite{Bern-Demaine-Eppstein-Kuo-Mantler-Snoeyink-2003,Demaine-O'Rourke-2007}.
In general, an \emph{unfolding} consists of cutting along the polyhedron's
surface such that what remains flattens into the plane without overlap.
Convex polyhedra have been known to unfold
since at least the 1980s \cite[Sec.~24.1.1]{Demaine-O'Rourke-2007}.

A recent breakthrough for nonconvex polyhedra is the unfolding of
any ``orthogonal'' polyhedron (homeomorphic to a sphere)
\cite{Damian-Flatland-O'Rourke-2007-epsilon}.
A polyhedron is \emph{orthogonal} if all of its edges are parallel
to a coordinate axis, and thus all edges and faces meet at right angles.
While very general, a disadvantage of this unfolding algorithm
is that the cutting is inefficient,
making exponentially many cuts in the worst case, 
resulting in an unfolding that is long and thin (``epsilon thin'').
         
In this paper, we show how to unfold any orthogonal polyhedron
using only a polynomial number of cuts.

\paragraph{Grid refinement.}
To more precisely quantify the cuts required by an unfolding,
several models of allowed cuts have been proposed.
See \cite{Demaine-O'Rourke-2005,Demaine-O'Rourke-2007,O'Rourke-2008-orthosurvey}
for surveys.

For convex polyhedra, the major unsolved goal is to just cut along the edges
(which implies a linear number of cuts) \cite[ch.~22]{Demaine-O'Rourke-2007}.
For nonconvex polyhedra, however, this goal is unattainable, even
when the polyhedron is ``topologically convex''
\cite{Bern-Demaine-Eppstein-Kuo-Mantler-Snoeyink-2003}
or is orthogonal
\cite{Biedl-Demaine-Demaine-Lubiw-Overmars-O'Rourke-Robbins-Whitesides-1998}.
A simple example of the latter is a small box on top of a larger box.
More generally, deciding whether an orthogonal polyhedron has an edge
unfolding is strongly NP-complete \cite{Abel-Demaine-2011}.

For orthogonal polyhedra, it seems most natural to consider orthogonal cuts.
The smallest extension from edge unfolding seems to be \emph{grid unfolding}
(a concept implicit in
\cite{Biedl-Demaine-Demaine-Lubiw-Overmars-O'Rourke-Robbins-Whitesides-1998}),
where we slice the polyhedron with all axis-aligned planes that pass through
at least one polyhedron vertex, and allow cutting along all slice lines.
Even with these additional edges, few nontrivial subclasses of
orthogonal polyhedra are known to have grid unfoldings: ``orthotubes''
\cite{Biedl-Demaine-Demaine-Lubiw-Overmars-O'Rourke-Robbins-Whitesides-1998},
``orthostacks'' composed of orthogonally convex slabs
\cite{Damian-Meijer-2004-orthostacks}, and
``well-separated orthotrees''
\cite{Damian-Flatland-Meijer-O'Rourke-2005-orthotrees}.
On the negative side, there are four orthogonal polyhedra with no
\emph{common} grid unfolding
\cite{Aloupis-Bose-Collette-Demaine-Demaine-Douieb-Dujmovic-Iacono-Langerman-Morin-2010}.

The next extension beyond grid unfolding is \emph{grid refinement} $k$,
which additionally slices with $k$ planes in between every grid plane
(as above), and allows cuts along any edges of the refined grid.
With constant grid refinement, a few more classes of orthogonal polyhedra
have been successfully unfolded: orthostacks
\cite{Biedl-Demaine-Demaine-Lubiw-Overmars-O'Rourke-Robbins-Whitesides-1998},
and Manhattan towers \cite{Damian-Flatland-O'Rourke-2008-manhattan}.

The breakthrough was the discovery that arbitrary orthogonal polyhedra
(homeomorphic to a sphere) unfold with finite grid refinement
\cite{Damian-Flatland-O'Rourke-2007-epsilon}.
Unfortunately, the amount of grid refinement is exponential
in the worst case (though polynomial for ``well-balanced'' polyhedra).
For this reason, the unfolding algorithm was called
\emph{epsilon-unfolding}.

\paragraph{Our results.}
We show how to modify the epsilon-unfolding algorithm of
\cite{Damian-Flatland-O'Rourke-2007-epsilon}
to reduce the refinement from worst-case exponential ($2^{\Theta(n)}$)
to worst-case quadratic ($\Theta(n^2)$), while still unfolding
any orthogonal polyhedron (with $n$ vertices) homeomorphic to a sphere.
We call our algorithm the \emph{delta-unfolding} algorithm,
to suggest that the resulting surface strips are still narrow
but wider than those produced by epsilon-unfolding.

Our central new technique in delta-unfolding is the concept of ``heavy''
and ``light'' nodes from ``heavy-path decomposition''
\cite{Sleator-Tarjan-1983}.  Interestingly, heavy-path decomposition
is a common technique for balancing trees in the field of data structures,
but not so well known in computational geometry.

Even with this technique in hand, however, delta-unfolding requires a
careful modification and engineering of the techniques used by
epsilon-unfolding.  Thus, Sections~\ref{sec:overview}
and~\ref{Epsilon-Unfolding Extrusions} start with reviewing the
main techniques of epsilon-unfolding; then Section~\ref{sec:Delta}
modifies those techniques; and finally
Section~\ref{Delta-Unfolding of Genus-Zero Orthogonal Polyhedra}
puts these techniques together to obtain our main result.


\section{Overview of Epsilon-Unfolding}
\label{sec:overview}

%Here
We begin with a review the epsilon-unfolding algorithm~\cite{Damian-Flatland-O'Rourke-2007-epsilon},
starting in this section with a high-level overview,
and then in Section~\ref{Epsilon-Unfolding Extrusions}
detailing those aspects of the algorithm
that we modify to achieve quadratic refinement.
%Section~\ref{sec:Delta} below details
%the differences between this epsilon-unfolding algorithm
%and the delta-unfolding algorithm we propose.

%\paragraph{General notation.}
%\xxx[JOR]{I changed $O$ to $P$ throughout.}
Throughout this paper,
$P$ denotes a genus-zero orthogonal polyhedron whose edges are parallel to the
coordinate axes and whose surface is a $2$-manifold.
We take the $z$-axis to define the \emph{vertical} direction,
the $x$-axis to determine \emph{left} and \emph{right},
and the $y$-axis to determine \emph{front} and \emph{back}.
%and the $y$-axis to determine \emph{forward} and \emph{rearward}.%
%
%\footnote{The awkward names ``forward'' and ``rearward'' are to avoid confusion
%  with other uses of ``front'' and ``back'' introduced later.}
%
We consistently take the viewpoint from $y=-\infty$.
The faces of $P$ are distinguished by their outward normal:
forward is $-y$; rearward is $+y$; left is $-x$; right is $+x$; bottom is $-z$;
top is $+z$.%
%
\footnote{The $\pm y$ faces are given the awkward names
  ``forward'' and ``rearward'' to avoid confusion with other uses
  of ``front'' and ``back'' introduced later.}
%\xxx[JOR]{This is sure to be controversial, but I thought I would try it...}


The epsilon-unfolding algorithm partitions $P$ into \emph{slabs}
%\xxx[JOR]{Warning: Later slabs are called ``boxes.''}
by slicing
it with $y$-perpendicular planes through each vertex. Let $Y_0, Y_1, Y_2, \dots$
be the slicing planes sorted by $y$ coordinate. A \emph{slab} %slab
$s$ is a connected component of
$P$ located between two consecutive planes $Y_i$ and $Y_{i+1}$.
Each slab is a simple orthogonal polygon extruded in the $y$-direction.
%\xxx[JOR]{Correct?  In other words, two boxes sharing a corner edge
%  constitute
%two slabs and not one?  Or maybe we exclude any $P$ that would have two
%boxes sharing an edge, as that surfaces is not a 2-manifold?
%I think the definition of $P$ might need clarification, perhaps by
%just saying: ``the surface of $P$ is a 2-manifold''...}
The cycle of
\{left, right, top, bottom\} faces surrounding $s$ is called a \emph{band}, and
the band edges in $Y_i$ (and similarly in $Y_{i+1}$) form a cycle called a \emph{rim}.
A $z$-\emph{beam} is a narrow vertical strip on a forward or rearward face of $P$
connecting the rims of two bands.
The order in which the bands unfold is determined
by an \emph{unfolding tree} $T_U$ whose nodes are bands,
and whose arcs correspond to $z$-beams, each of which connects a
parent band to a child band in $T_U$. The unfolding tree
%with the parent-child arc connecting two bands corresponding to a
%$z$-\emph{beam},
%a narrow vertical strip on a forward or rearward face of $P$
%that connects the rims of the bands.
$T_U$ will be further described in Section~\ref{sec:Tree} below.

The unfolding of a band $b$ is determined by
a thin surface spiral, %path,
denoted $\xi$, that starts on one of $b$'s rims,
cycles around $b$ %, displacing in each loop a bit
while displacing toward the other rim, where it
turns around and returns to the point
it started.  As the spiral passes by a $z$-beam connecting $b$ to one of its children, %a child,
it enters through the $z$-beam to the child's rim, and then recursively
visits the subtree rooted at the child.
Once the complete spiral %path
is determined, it can be thickened in the $\pm y$ direction so that
it entirely covers all band faces.
The thickened spiral %path
is such that it can be laid flat in the plane to form a
monotonic staircase strip. The forward and rearward faces of $P$ can then be laid flat without overlap
by attaching them in strips above and below the staircase.

\section{Epsilon-Unfolding Extrusions}
\label{Epsilon-Unfolding Extrusions}

Almost all algorithmic issues in epsilon-unfolding are present in unfolding polyhedra
that are $z$-extrusions of simple orthogonal polygons in the $xy$ plane.
Therefore, we follow~\cite{Damian-Flatland-O'Rourke-2007-epsilon} in describing
the algorithm for this simple shape class, before extending the ideas
to all orthogonal polyhedra.  All modifications needed for
delta-unfolding
%quadratic refinement
are also present in unfolding orthogonal extrusions, and so we
describe them in terms of this simple shape class.
We therefore review in detail the epsilon-unfolding algorithm for orthogonal extrusions.

\subsection{Unfolding Tree}
\label{sec:Tree}
Let $P$ be a polyhedron that is the vertical extrusion of a simple orthogonal polygon, such
as that illustrated in Figure~\ref{fig:partition}a.
The algorithm
begins by slicing $P$ into slabs, which in this special case are all
blocks (cuboids),
using $y$-perpendicular planes through each vertex.
%[MD] This is already mentioned in the previous section
%The top, left, bottom, and right faces of each box form a band.
The dual graph is a tree, $T_U$, having a node for each band and an edge
between each pair of adjacent bands.
In this special case, all $z$-beams are degenerate, i.e., of zero $z$-height.
The root is selected arbitrarily from among
all bands with a rim of
minimum $y$ coordinate. For example, the
polyhedron in Figure~\ref{fig:partition}a is sliced into nine
blocks, with $b_1$ as the root and
its unfolding tree as shown in Figure~\ref{fig:partition}b.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure Begin
\begin{figure}[htbp]
\centering
\includegraphics[width=.7\linewidth]{partition}
%\fbox{partition}
\caption{(a) Extrusion of an orthogonal polygon, partitioned by $y$ perpendicular planes. (b) Unfolding
  tree. Back children are represented by shaded nodes.}
\label{fig:partition}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure End
%\xxx[JOR]{I think it is confusing to use $b$ for front and $c$ for
%  back.
%And doubly confusing because all other figures use $b$ alone.
%I recommend that front and back be distinguished by shading
%(the thickened arcs we used in EpsUnf were not a good idea!}

The rim of the root band with the
smaller $y$ coordinate is its \emph{front rim}, and the other rim
is its \emph{back rim}. For any other band, the rim adjacent to its parent in $T_U$ is
its front rim, and its other rim is its back rim.
Children attached along the front rim of their parent are \emph{front children}; children attached
along the back rim of their parent are \emph{back children}.
Note that ``front'' and ``back'' modifiers for rims and children derive from the structure of
$T_U$, and are not related to the ``forward'' and ``rearward'' $\pm y$
directions.
For example, $b_9$ is a front-child of $b_8$, although it is attached
to
the rearward face of $b_8$, and the front rim of $b_5$ lies
%partially
on the rearward face of $b_5$.
%\xxx[JOR]{Adjust if you follow my advice re $b$ and $c$.}


\subsection{Recursive Unfolding}

The key to the epsilon-unfolding method is the existence of a thin, non-crossing %path
\emph{spiral} $\xi$ that cycles around each band
at least once, and unfolds to a staircase when flattened into the
plane.
A \emph{staircase} is an orthogonal path in the plane whose turns
alternate between $90^\circ$ left and  $90^\circ$ right, and so is a
monotone path.
The path that $\xi$ follows is determined recursively.
%
%Next
We review this \emph{spiral} %path
$\xi$, starting with the base case.

\subsubsection{Single Band Base Case}
\label{sec:basecase}

Figure~\ref{fig:Rts}a shows the path followed by $\xi$ %follows
for a single band corresponding to a leaf of $T_U$.
It starts at an \emph{entering point} $s$ on the top edge of
the front rim and spirals in a clockwise direction %(as viewed from $y=-\infty$)
around the top, right, bottom, and left band faces %(labeled $T$, $R$, $B$, and $L$)
toward the back rim. %This portion of the path is shown in gray.
We call this spiral piece up to the point it reaches the back rim the
\emph{entering spiral}.
When it reaches the back rim, $\xi$ %it
crosses the rearward face upward toward the top face.
% from $B$ to the rearward face $K$, and then moves up $K$ to $T$.
From there, it retraces the entering spiral in the opposite (counterclockwise)
direction toward an \emph{exiting point} $t$  lying next to $s$ on
the front rim.
%spirals back in a counterclockwise direction to . This portion of the path is  blue.
When $\xi$ is cut out, unfolded, and laid horizontally in the plane,
it forms a monotonic staircase strip, as shown in
Figure~\ref{fig:Rts}b, because the turns alternate between left and
right, $90^\circ$ each.
Observe that
the $x,z$-parallel segments of $\xi$, corresponding to the cycling
clockwise and counterclockwise around the band, form the stair ``treads'';
the $y$-parallel segments of $\xi$ and the $z$-parallel strip from the rearward face
form the stair ``risers.''
%\xxx[JOR]{These are so-called ``scare quotes,'' to indicate special
%  meanings, but not quite formal definitions.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure Begin
\begin{figure}[htbp]
\centering
\includegraphics[width=\linewidth]{Rts}
%\fbox{Rts}
\caption{(a) $R_{ts}$ block spiral, with
mirror views of faces that cannot be seen directly.
(b) Unfolded spiral.
(c) Abstract 2D representation.}
\label{fig:Rts}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure End
%\xxx[JOR]{Part (c) needs $x$- and $y$-axis arrows, as the view is
% turned from part (a).
%I would recommed that the white faces be light gray?  In my copy they
%are nearly invisible.}
%\xxx[JOR]{I do agree that this figure needs to be metrically accurate,
%  because this is where the 1st-time reader is trying to piece it
%  together,
%and it confuses to have inaccurate lengths.}

Three-dimensional illustrations of $\xi$ like that in Figure~\ref{fig:Rts}a
are impractical for
more complex orthogonal shapes. To easily illustrate more complex unfoldings, we
%a 2D representation is used, as
use the 2D representation
depicted in Figure~\ref{fig:Rts}c.
Note that the 2D representation captures the direction of the entering spiral and
the relative position of $s$ and $t$. The arc connecting the entrance to the exit
symbolizes the reversal of the unfolding direction
using a rearward face strip.

Eight variations of the base case spiral are illustrated in Figure~\ref{fig:R}.
They differ in the manner in which $\xi$ enters and exits the band $b$ to be unfolded.
The four variations labeled $L_{ts}$, $L_{st}$, $R_{ts}$, $R_{st}$ in the top row are
used when the $y$-coordinate of $b$'s %block's
front rim is smaller than %less than (i.e., more forward than)
the $y$-coordinate of its back rim. $R_{st}$ is %the same as
similar to $R_{ts}$, but %reversing
with $s$ and $t$, and the clockwise/counterclockwise
cycling direction reversed; $L_{ts}$ and $L_{st}$ are (respectively) mirrors of
$R_{st}$ and $R_{ts}$ in an $x$-perpendicular plane. Note that the $R$ and $L$ labels indicate
the spiral's cycling direction when it enters the band: $R$ is clockwise,
$L$ is counterclockwise. The spiral exits the band cycling in the opposite direction.
The four variations in the bottom row
are labeled $L^{+}_{ts}, L^{+}_{st}, R^{+}_{ts}, R^{+}_{st}$, and they are
used when
the $y$-coordinate of $b$'s front rim is greater than the $y$-coordinate
of its back rim.
They are exact reflections of $L_{ts}$, $L_{st}$, $R_{ts}$, and $R_{st}$, respectively, in
a $y$-perpendicular plane.
The mirror symmetries imply that the 3D spiral corresponding to each 2D
abstract representation can be easily derived from $R_{ts}$ configuration, illustrated in Figure~\ref{fig:Rts}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure Begin
\begin{figure}[htbp]
\centering
\includegraphics[width=0.8\linewidth]{R}
%\fbox{R}
\caption{Abstract 2D representations of the eight path types visiting one slab.}
\label{fig:R}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure End

%There are eight variations of this spiraling path, which differ in the
%manner in which $\xi$
%enters and exits the band:
%the spiral enters a band
%cycling either clockwise (heading to the right from $s$) or counterclockwise
%(heading to the left from $s$), $t$ is
%either to the right or to the left
%of $s$ on the top edge, and
%the front rim is either the rim of lower $y$-coordinate or the rim of higher $y$-coordinate.
%Directions clockwise, counterclockwise, left, and right, are defined w.r.t a
%viewer at $y = -\infty$ looking at the band.
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure Begin
%\begin{figure}[htbp]
%\centering
%\includegraphics[width=0.8\linewidth]{R}
%%\fbox{R}
%\caption{Abstract 2D representations of the eight path types visiting one slab.}
%\label{fig:R}
%\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure End
%%
%The labels $L_{st}, L_{ts}, R_{st}, R_{ts}$ are used to identify the
%four possible entering/exiting configurations for the case when the $y$-coordinate
%of the front rim is less than (i.e., more forward than)
%the $y$-coordinate of the back rim. The corresponding
%2D representations are depicted in the top row of Figure~\ref{fig:R}.
%Here the first letter ($L$ or $R$)
%indicates the direction (Left or Right, counterclockwise or clockwise) the spiral is
%cycling when it enters the band at $s$, and the subscripts indicate the position of $s$ relative to $t$ on the
%top edge.  The labels also imply the direction in which $\xi$ is cycling
%when it exits at point $t$, since it is always the opposite of the entering direction.
%Note that $R_{st}$ is identical to $R_{ts}$, with the exception of the unfolding
%direction, which is opposite, and the relative position of $s$ and $t$, which is
%reversed. Also note that $L_{st}$ and $L_{ts}$ are mirrors of $R_{st}$ and $R_{ts}$
%respectively, with respect to an $x$-perpendicular plane (in 3D).
%%
%For the case when the $y$-coordinate of the front rim is higher than the $y$-coordinate of
%the back rim, the 2D unfolding representations are depicted in the bottom row of
%Figure~\ref{fig:R}, and are labeled  $L^{+}_{st}, L^{+}_{ts}, R^{+}_{st}, R^{+}_{ts}$.
%Note that these are exact reflections of
%$L_{st}, L_{ts}, R_{st}, R_{ts}$ respectively, with respect to a
%$y$-perpendicular plane. This implies that each of the eight types of
%3D unfolding can be easily derived from $R_{ts}$, illustrated in
%Figure~\ref{fig:Rts}a.
%
%\xxx[JOR]{I think this paragraph could be rewritten to be less
%  verbose, more formalized, and more clear.  (Sorry, I didn't actually
%  do it.)
%$L_{ts}$ is the mirror of $R_{st}$ in an $x$-plane.
%Etc.  So I think you can define all eight by describing one,
%$L_{ts}$, saying $L_{st}$ is the same but reversing $s$ and $t$ and cw/ccw,
%and then
%mirroring in either $x$- or $y$-planes to get all others.
%(Incidentally, I would prefer ``$y$-plane'' to ``$y$-perpendicular
%plane'' throughout, but my feeling isn't strong so I won't make that
%change.)
%The $x$-plane mirrors naturally reverse $s$ and $t$, while the
%$y$-plane
%mirrors do not. Both mirrors reverse cw and ccw.}

\subsubsection{Recursive Path}
\label{sec:eps-recursive}

For a node $b$ in $T_U$ that is not a leaf, we describe the path that the spiral $\xi$
recursively follows when visiting $b$.
We assume that $b$ has one of the eight configuration
labels shown in Figure~\ref{fig:R}.
As in the base cases, the label
identifies the relative order of points $s$ and $t$ on $b$'s front rim, the spiral's direction
when entering %and leaves
$b$, and %which of
$b$'s rim %has
of lower $y$ coordinate.
% and identified points $s$ and $t$
%on the top edge of its front rim such that their relative
%position
%is consistent with the assigned label.
Without loss of generality, we assume that
$b$'s label is $R_{ts}$; the other seven labels are equivalent by symmetry.
% With the $R_{ts}$ label, $\xi$ enters at point $s$ cycling clockwise around $b$,
% and it must exit $b$ at point $t$ (located left of $s$)
% cycling in the opposite direction.
%\xxx[JOR]{I removed a sentence here that seems redundantly explicit.}
The inductive assumption is
that, for any subtree %of height smaller than
shorter than the subtree of $T_U$ rooted at $b$, and for
any configuration label assigned to the root band of the shorter subtree,
%if the root band of the smaller
%subtree is assigned any of the four labels and entering and exiting points
%are identified on its top front edge, then
there is a (non-crossing) path $\xi$ consistent with that label
that cycles around each band in the smaller subtree at least once,
and unfolds in the plane as a staircase strip.
%similar to the one from Figure~\ref{fig:Rts} for the base case.
%\xxx[JOR]{Phrase no longer needed because now there is a definition of ``staircase'' above.}

After $\xi$ enters $b$ at point $s$,
% cycling clockwise,
it visits each of
$b$'s front children,
starting with the front child, call it $b_1$,
first encountered as it cycles clockwise along the front rim of $b$.
%that it passes when moving on the top face of $b$.
(See Figure~\ref{fig:epsfrontchildren}).
For reasons soon to be explained,
child $b_1$ is assigned the label $R^{+}_{st}$ with two points
$s_1$ and $t_1$ identified on the top edge of its front rim, with $t_1$
right of $s_1$.
The spiral $\xi$
%makes a $90^\circ$ turn, moves parallel to \red{$x$}
enters $b_1$ at point $s_1$ and recursively visits it (and the subtree
it roots).
By the inductive hypothesis, $\xi$ exits $b_1$ at point $t_1$ cycling counterclockwise.
The label $R^{+}_{st}$ is assigned to $b_1$ because
$\xi$ is cycling in the direction $R$ (to the right, or clockwise)
on $b$ just before it enters $b_1$, and so it enters
$b_1$ with that same direction; the $+$ superscript is necessary
because the $y$-coordinate of the front rim of $b_1$ is %larger
higher than
that of its back rim; and the
$\nothing_{st}$ ordering is necessary to prevent $\xi$ from being
trapped beneath the portion of $\xi$ between $s$ and $s_1$ upon
returning to $b$, thus cutting itself off from reaching $b$'s other children
(because it cannot cross itself).


% [MD] Modified the figure below further (removed the 5th child).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure Begin
\begin{figure}[htbp]
\centering
\includegraphics[width=0.9\linewidth]{epsunffront}
%\fbox{epsunffront}
\caption{Nested inside-out alternating path visits the front children. Dotted lines show $\xi$
where it cycles underneath on the bottom face.}
\label{fig:epsfrontchildren}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure End
%\xxx[JOR]{The $s$ and $t$ label subscripts in $b_2$ and $b_3$ are incorrect.}

After recursively visiting $b_1$, $\xi$ %then
cycles counterclockwise on $b$
to the first unvisited child it passes when on $b$'s top face. This child, call it $b_2$,
is assigned the label $L^{+}_{ts}$ with identified points $t_2$ and $s_2$ on its front
rim, consistent with its label,  and it is recursively visited.
In this nested manner, $\xi$ visits the
children clockwise and counterclockwise from $s$ from the inside out,
alternately assigning the labels $R^{+}_{st}$ and $L^{+}_{ts}$.
Figure~\ref{fig:epsfrontchildren} illustrates the path $\xi$ takes
when $b$ has four
front children. (To keep the example simple, only
one level of recursion is illustrated, with all children leaves of $T_U$.)

% [MD] Modified the figure below (removed the 5th child).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure Begin
\begin{figure}[htbp]
\centering
\includegraphics[width=0.9\linewidth]{epsunfback}
%\fbox{epsunfback}
\caption{Nested outside-in alternating path visits the back children.}
\label{fig:epsbackchildren}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure End
%\xxx[JOR]{I think a pair of $x/y$-axis arrows would be helpful here
%(and in almost every figure).  It is so easy to get lost!}

After visiting the front children, $\xi$ makes a complete cycle around $b$ and
then begins visiting the back children. Assume for concreteness that after visiting the
front children, $\xi$ is cycling %counter-
clockwise on $b$, as shown in Figure~\ref{fig:epsbackchildren}. It then travels %counter-
clockwise to the back child farthest to the right
along the top face. (See child $b_5$ in Figure~\ref{fig:epsbackchildren}).
When it returns from recursively visiting this back child, it will be cycling counterclockwise
(by the inductive hypothesis).
It is thus important that the child's exit point be to the left
of its entering point so that $\xi$ is not blocked from visiting other back children.
(See points $s_5$ and $t_5$ in Figure~\ref{fig:epsbackchildren}.)
Thus this first back child is assigned the configuration %$L_{st}$
$R_{ts}$ and is recursively visited.  The spiral then moves to the unvisited child
farthest to the left
(see child $b_6$) and visits it in a similar way, assigning it the label $L_{st}$.
Thus the nesting of $\xi$'s alternating path is outside-in for back children,
with the labels $R_{ts}$ and $L_{st}$ being alternately assigned.
%\xxx[JOR]{It may be possible to augment this description with mirror
%  reflections,
%because the various config labels are merely $x$-plane reflections of
%one another as the path moves left and right.}

The last back child visited, $b_k$, however, is an exception when it comes to
its label assignment, for the following reason.
When the spiral exits $b_k$ (see $b_{8}$ in Figure~\ref{fig:epsbackchildren}),
it will retrace its path (in reverse direction) back
to the front rim of $b$ and then exit at point $t$.
For band $b$,  define its \emph{entering spiral}, $\xi_e(b)$, to be the portion of $\xi$ that begins
at $s$ and ends at the exiting point $t_k$ of $b_k$
($t_{8}$ in Figure~\ref{fig:epsbackchildren}).
Its \emph{exiting spiral}, $\xi_x(b)$, is the portion of $\xi$ that
begins at $t_k$
%the exiting point of $b_k$
%($t_{8}$ in Figure~\ref{fig:epsbackchildren})
and ends at $t$ on the front rim of $b$.
The exiting spiral $\xi_x(b)$ simply parallels alongside the
entering spiral $\xi_e(b)$,
retracing the portion of $\xi_e(b)$ from $s$ to $s_k$ but in the opposite direction.
Since $b$ has a $\nothing_{ts}$ label, the exiting spiral must leave $b$ with the entering
spiral on its left, from the point of view of one walking on $b$
along the path taken by $\xi_x(b)$. Thus $b_k$
must also be assigned the label $\nothing_{ts}$ (consistent
with  $b$'s label), so that from the beginning of the retrace and throughout, $\xi_x(b)$ has
the entering spiral to its left. We call this a \emph{left retrace}; when $\xi_x(b)$ keeps
the entering spiral on its right during a retrace, we call it a \emph{right retrace}.
We note that if $b$ has no back children,
then the spiral reverses direction using a strip from $b$'s rearward face, as in
the base cases.

\subsection{Completing the Unfolding}
\label{sec:frontback}

We have focused on $\xi$'s recursive path because that is where the modifications
for delta-unfolding occur. But for completeness, we briefly summarize the
remainder of the epsilon-unfolding algorithm for extrusions, and
refer the reader to~\cite{Damian-Flatland-O'Rourke-2007-epsilon} for  additional details.
To complete the unfolding of $P$, $\xi$ is thicken in the $+y$ and $-y$ direction (as viewed
in the 3D coordinate system of Figure~\ref{fig:Rts}a) so that it completely covers
each band. This results in a thicker unfolded staircase strip. Then the
forward and rearward faces of $P$ are partitioned by imagining the band's top rim edges illuminating downward light rays in these
faces. The illuminated pieces are then ``hung" above and below the thickened staircase,
along the corresponding illuminating rim segments which lie along the horizontal edges of
the staircase.

\subsection{Level of Refinement}

In~\cite{Damian-Flatland-O'Rourke-2007-epsilon} it was shown that the unfolding technique discussed so far %this technique
can make an exponential
number of cuts on the family of polyhedra
depicted in Figure~\ref{fig:expcase}. Each polyhedron consists of $n =
2k+1$, $k \geq 1$, blocks
%\xxx[JOR]{I think this is the first use of ``block'' to replace
%  ``box'' (which replaced ``slab'').
%Maybe it should be slab for the general case, block for the special
%case,
%and box should not be used?}
arranged as shown for $k = 1$ in Figure~\ref{fig:expcase}a, and for $k=2$ in Figure~\ref{fig:expcase}b. For analysis purposes, we formally define a \emph{visit} to a band to begin
when the spiral crosses its front rim to enter the band (either the first time, or in a retrace) and
end when it crosses the front rim to exit the band.
%\xxx[JOR]{for the last time?  If so: should be said explicitly.}
In Figure~\ref{fig:expcase}a, $b_3$'s visit begins when $\xi$ enters it at
point $s_3$ cycling counterclockwise. The spiral visits back child
$b_1$ and then $b_2$. The visit of $b_2$ triggers a retrace which involves a second visit of $b_1$, and then
back through $b_3$ to exiting point $t_3$, which completes $b_3$'s visit.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure Begin
\begin{figure}[htbp]
\centering
\includegraphics[width=\linewidth]{expcase}
%\fbox{expcase}
\caption{Family of polyhedra requiring exponential refinement. Block $b_1$ is visited two times in (a), four times in (b), and in general $2^{\lfloor n/2 \rfloor}$ times for an $n$-block object.}
\label{fig:expcase}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure End
We can write this visit order using the string
$Q_3 = (s_3 ~(s_1~  t_1)~ (s_2 ~t_2)~ (s_1~ t_1)~ t_3)$, where an open parenthesis followed by a starting point
marks the start of a visit and  an exiting point followed by
a closing parenthesis marks the end.
The subscript on $Q$ is the number of blocks in the polyhedron. Observe that block $b_1$
is visited twice.
For the five block polyhedron in
Figure~\ref{fig:expcase}b, $\xi$ starts at point $s_5$ on $b_5$,
recursively visits block $b_3$ in the
manner just described, then visits $b_4$ which triggers a retrace through $b_3$.
After revisiting $b_3$, $\xi$ returns to $b_5$ and exits at point $t_5$. The corresponding visit string is
$Q_5 = (s_5~Q_3~ (s_4~t_4)~Q_3~ t_5) $.
The number of visits to $b_1$ doubles to $4$. In general,
an $n$ block polyhedron in this family gives rise to
$2^{\lfloor n/2 \rfloor}$ visits to $b_1$, resulting in an exponential
number of cuts on $b_1$.

\section{Delta-Unfolding Extrusions}
\label{sec:Delta}

To achieve quadratic refinement, we modify the
order in which children are visited
based on the heavy/light classification of nodes used in
\emph{heavy-path decomposition}~\cite{Sleator-Tarjan-1983}.
%of $T_U$
%
%to reduce the
%number of times the spiral revisits deep subtrees in the unfolding
%tree.
In heavy-path decomposition,
each tree node $v$ is
assigned a weight $n(v)$, which is the number of descendants in its
subtree, including itself.  An edge from parent $p$ to child $c$ is
\emph{heavy} if $n(c) > \frac{1}{2}n(p)$, and \emph{light} otherwise. We say a child
$c$ is \emph{heavy} (\emph{light}) if the edge between $c$ and its parent is heavy (light). Observe that
a node can have at most one heavy child.

If a node $b$ in $T_U$ has a heavy child, then we modify the
path of the entering spiral $\xi_e(b)$ so
that it visits the heavy child last, to prevent the need for revisiting the heavy child; we %which we
will show that this strategy quadratically bounds the
number of visits $\xi$ makes to each child.
%
For example, consider the polyhedron in Figure~\ref{fig:expcase}b, and observe that
% that lead to exponential
%refinement. Each parent
%band $b_i$ has two children --- the right one corresponding to a leaf node in the unfolding tree
%and the left one, $b_{i-2}$, rooting a subtree of $i-2$ nodes.
$b_3$ is a heavy child. With epsilon-unfolding, $\xi_e(b)$ visited child $b_3$
before $b_4$. The visit to $b_4$ triggered a complete retrace of the subtree rooted
at $b_3$, thus leading to the visit string $Q_5 = (s_5~Q_3~ (s_4~t_4)~Q_3~ t_5)$,
and a total of four visits to $b_1$.
%and only then
%is the leaf child visited.
%The visit to the leaf child triggers a retrace of the heavy child (and all
%its descendents in the unfolding tree), resulting in exponential visits to the deepest
%node. By reversing the visit order and visiting the heavy child
%last for each band, it is the heavy child that triggers the retrace and the
%retrace is minimal, involving only the leaf child. Each heavy child is
%then visited once, the leaf children are each visited twice, and
%we avoid an exponential number of visits.
But if we reverse the visit order so that $\xi_e(b)$ visits $b_3$ after $b_4$,
then the visit
string becomes $Q'_5 = (s_5~(s_4~t_4)~Q_3~(s_4~t_4)~t_5)$, and no
block is visited more than twice.
%\xxx[JOR]{I think you need to use (b) of the figure, because (a) is
% balanced left/right, and the ordering you detail makes no
% difference.
%The point would be more forceful if you could explicitly compare
%the visit string $Q_5$ you listed above with the alternative $Q'_5$.}

Since any front or back child could be heavy, we focus first on the challenge of
finding a route for the entering spiral so that it visits any specified child
last.
If we can achieve this, then we can organize the visits to minimize
retracing.
%\xxx[JOR]{Right?  It is at this point not clear exactly why this is
%  the focus.  There needs to be presaging of what's to come...}
%We start with the case when the last child to be visited is
%a front child, and then discuss the case when it is a back child.
We then
formally present the algorithm and
analyze the resulting level of refinement.

\subsection{Front Child Visited Last}
\label{sec:heavyfront}

We start with the case when we desire to visit
a front child, call it $b_\ell$, last.
The idea is to visit all the front children excluding $b_\ell$,
and all the back children in exactly the %same manner as
manner described in Section~\ref{sec:eps-recursive}, as if $b_\ell$ were not present.
Figure~\ref{fig:unfex} shows the entering spiral $\xi_e(b)$ visiting all
but $b_\ell$.
(Note that the complete cycle that $\xi_e(b)$ makes between
 visiting the front and back children is not fully depicted in the
2D representation.)
After visiting the last back child ($b_9$ in the figure), $\xi$ retraces its
path in reverse.
It is during this retrace step that child $b_\ell$ is visited.
We explain the modifications necessary to accomplish this for a parent block
$b$ with a label of type $R_{\nothing}$ or $L_{\nothing}$; labels of type $R^+_{\nothing}$ and $L^+_{\nothing}$ are handled symmetrically.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure Begin
\begin{figure}[htbp]
\centering
\includegraphics[width=0.8\linewidth]{unfex}
%\fbox{unfex}
\caption{Entering spiral  visits front and back children, with the exception of front child $b_\ell$,
which gets visited last (see Figure~\ref{fig:unfex2}).}
\label{fig:unfex}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure End

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure Begin
\begin{figure}[htbp]
\centering
\includegraphics[width=0.8\linewidth]{unfex2}
%\fbox{unfex2}
\caption{Entering and return spirals. The return spiral passes by $b_\ell$ so that $b_\ell$
can be visited.}
\label{fig:unfex2}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure End

Observe first  that since $\xi_e(b)$ alternately visits all the front children
except for $b_\ell$ and then makes a complete cycle
around $b$,
some contiguous section of it, call it $f$, runs
alongside the top edge of $b_\ell$'s front rim.
Specifically, $f$ is the section of $\xi_e(b)$ hit by $y$-parallel rays shot from
$b_\ell$'s top front rim edge toward the back rim of $b$. See Figure~\ref{fig:unfex} where
$f$ is marked. Note that since
$\xi_e(b)$ is cycling toward the back rim of $b$, $f$ represents the first
time $\xi_e(b)$ %it
passes by $b_\ell$'s top edge.
All subsequent passes are behind $f$.

During the retrace step,
 $\xi$ needs to run in front of $f$, so that it has unobstructed
access to $b_\ell$.
If the entering spiral
is cycling clockwise in section $f$, then the retracing spiral (which runs alongside
$f$ in the opposite direction) needs to
right-retrace, because that will keep the entering spiral to its right and
position it in front of $f$.
(Recall that clockwise is to the right and counterclockwise is
to the left.)
To trigger a right-retrace, we assign the last visited back child the label $\nothing_{st}$.
If the entering spiral
is cycling counterclockwise in section $f$, then the retracing spiral needs to
left-retrace, thus keeping the entering spiral on its left.
To trigger a left-retrace, we assign the last back child the label $\nothing_{ts}$.
So instead of matching the $\nothing_{st}$ or $\nothing_{ts}$ label of the last visited back
child to that of $b$ (as in epsilon-unfolding),
we instead assign it so that the retracing spiral passes alongside $b_\ell$.
When the retracing spiral reaches section $f$, it suspends
the retrace, enters $b_\ell$ at point $s_\ell$, and visits it. We call the portion of $\xi$
from the exiting point of the last visited back child to $s_\ell$ the
\emph{return spiral} and label it $\xi_r(b)$. See Figure~\ref{fig:unfex2}
which shows $\xi_r(b)$ in red extending from $t_9$ to $s_\ell$.
%\xxx[JOR]{Colors will (eventually?) not be available. :-/  But OK for
% the arXiv version (which may be the only version).  So: OK to retain color!}

Upon exiting $b_\ell$ at point $t_\ell$, the spiral retraces its path
in the reverse direction, bringing it to the exit point $t$ on $b$.
Specifically, it follows the entire path from $s$ to $s_\ell$ in reverse.
This second retrace is $b$'s exiting spiral, $\xi_x(b)$.
(In Figure~\ref{fig:unfex2}, $\xi_x(b)$ is not illustrated, but
it begins at $t_\ell$ and follows the red and then the black path
to $t$, keeping them to its left.)
The label $\nothing_{st}$ or $\nothing_{ts}$ assigned to $b_\ell$ must be consistent
with %that of
$b$'s label in the following way. If $b$ has the label $\nothing_{ts}$, a left retrace
starting from $t_\ell$ is needed so that the spiral exits at $t$ on
the correct side of $s$ consistent with $b$'s $\nothing_{ts}$ label. Thus,
$b_\ell$ is assigned the label $\nothing_{st}$, the opposite of $b$'s label. If, however, $b$ has the label $\nothing_{st}$,
a right retrace is needed, and so $b_\ell$ is assigned the label $\nothing_{ts}$.

Because the label assigned to the last back child visited depends
on the direction of $\xi_e(b)$ in the $f$-section of the path, we show here that
determining that direction is straightforward.
We discuss the case in which $\xi_e(b)$ enters $b$
cycling clockwise; the case when it is cycling counterclockwise
is symmetric. We also assume that there are at least two front children
(not including $b_\ell$) and
they are labeled $b_1$, $b_2$, $b_3, \dots$,
in the order in which they are visited along the alternating path (as in Figure~\ref{fig:unfex}).
Observe that, if $b_\ell$ is located between $s$ and $b_1$ (as viewed from above),
then $\xi_e(b)$ first passes by $b_\ell$'s top edge cycling clockwise, and
the same is true if it is located between $b_i$ and $b_{i+2}$,
for $i$ odd ($i \in \{1, 3, 5, \dots\}$). Thus in these cases, $f$ is traversed clockwise.
If $b_\ell$ is located between $s$ and $b_2$ or
between $b_i$ and $b_{i+2}$, for $i \in \{2,4,6,\dots \}$, then
$\xi_e(b)$ first passes by the top edge of $b_\ell$ cycling counterclockwise. Thus
in these cases $f$ is traversed counterclockwise.
If the top edge of $b_\ell$ is to the right of the last  odd
numbered child or to the left of the last even numbered child, then
$\xi_e(b)$ first passes over $b_\ell$ during its complete cycle around $b$.
During this cycle, $\xi_e(b)$ is heading
clockwise  if the last visited child was even and counterclockwise
if the last visited child was odd. Cases when there are fewer than two
front children are easily handled: if $b_\ell$ is the only front child,
or if it is located between $s$ and $b_1$, then then $f$ is traversed clockwise;
otherwise, $f$ is traversed counterclockwise.
%\xxx[JOR]{I am feeling a need for an explicit identification of:
%clockwise=right and ccw=left. Much earlier.  Did not find the spot,
%but could you please make this identification?}

\subsection{Back Child Visited Last}
\label{sec:heavyback}

In this section we discuss the situation in which we desire
to visit a particular back child $b_\ell$ last.
%\xxx[JOR]{Again the reader (me) needs to know why this is needed, in
%  that Intro section.}
In this case, $\xi_e(b)$ visits the front children as described in
Section~\ref{sec:eps-recursive}. It then visits the back children as described
in Section~\ref{sec:eps-recursive} but with an altered visiting order.
%The assignment of
%entering/exiting configuration labels
%($L_{st}$, $L_{ts}$, $R_{st}$, $R_{ts}$) to the back children
%is similar to that described in section~\ref{sec:eps-recursive},
%but with an altered visiting order.
We consider the case when $b$ has a $L_{\nothing}$ or $R_{\nothing}$ type configuration
label and the
entering spiral $\xi_e(b)$ is cycling counterclockwise after visiting the front children;
the other cases are symmetric.

Let $m \geq 0$ be the number of back children of $b$ not including $b_\ell$,
and let $b_1, b_2, \dots b_j$ be the front children, for $j \geq 0$.
Consider the back children of $b$ in the cyclic clockwise order in which their top edges
occur around $b$'s back rim.
When $m$ is odd, we label the $m$ back children
$(b_{j+1}, b_{j+3}, \dots, b_{m-2},  b_m, b_\ell, b_{m-1}, \dots,  b_{j+4}, b_{j+2})$,
according to their positions relative to $b_\ell$ in this cyclic ordering.
% as follows:
When $m$ is even, the labeling is %we label the back children
$(b_{j+1}, b_{j+3}, \dots, b_{m-1}, b_\ell, b_{m}, \dots,  b_{j+4}, b_{j+2})$,
as depicted in Figure~\ref{fig:unfback}. The spiral
$\xi_e(b)$ visits the back children from the outside-in, following the visit order
$b_{j+1}, b_{j+2}, \dots, b_{m-1}, b_{m}, b_\ell$.
It is always possible to visit $b_{j+1}$ first,
with a full cycle of the spiral around $b$ (if necessary) to get the spiral
to the top edge of $b_{j+1}$. This is illustrated in Figure~\ref{fig:unfback}
for five back children (and no front children).



%Let $k$ be the number of back children of $b$ including $b_\ell$,
%and let $j$ be the number of front children.
%We label the back children $b_{j+1}, b_{j+2}, ..., b_{j+k}$ in clockwise order
%of their top edges around the band such that the middle child in this ordering,
%$b_{\lceil ((j+1) + (j+k))/2 \rceil} = b_{\lceil (2j + k + 1)/2 \rceil}$, is child $b_\ell$.
%\red{(See Figure~\ref{fig:unfback}.)} The spiral
%$\xi_e(b)$ visits the children from the outside-in using the visiting order
%$b_{j+1}, b_{j+k}, b_{j+2}, b_{j+k-1}, b_{j+3}, \dots,
%b_{\lceil (2j + k + 1)/2 \rceil} = b_\ell$. It is always possible to visit $b_{j+1}$ first,
%with a full cycle of the spiral around $b$ (if necessary) to get the spiral
%to the top edge of $b_{j+1}$. This is illustrated in Figure~\ref{fig:unfback}
%for five back children (and zero front children).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure Begin
\begin{figure}[htbp]
\centering
\includegraphics[width=0.8\linewidth]{unfback2}
%\fbox{unfback2}
\caption{Labels and path followed by spiral when visiting back children, when the last child
to be visited is back child $b_\ell$;
%Labeling and unfolding method for back children, for fixed back child $b_\ell$ to be visited last;
dashed
lines depict spiral pieces on the bottom of the parent block.}
\label{fig:unfback}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure End

The assignment of $L_{\nothing}$ and $R_{\nothing}$ labels to the back children of $b$ is the same as described
in Section~\ref{sec:eps-recursive}.
Specifically, the labels for the children alternate between $L_{st}$
and $R_{ts}$ with respect to the visiting order.  The spiral $\xi_e(b)$ is cycling
counterclockwise (to the left) when it reaches $b_{j+1}$, which
matches $b_{j+1}$'s $L_{\nothing}$ label.
The recursive unfolding of $b_{j+1}$ reverses the direction of the spiral, so
that it enters
%$b_{j+k}$
$b_{j+2}$
cycling clockwise (to the right), thus matching
%$b_{j+k}$'s
$b_{j+2}$'s $R_{\nothing}$ label,
and similarly for the other back children.  The
alternating $\nothing_{st}$, $\nothing_{ts}$ labels of the children ensures an outside-in
nesting of $\xi$, which enables %allows
it to reach each back
child.  As in Section~\ref{sec:eps-recursive}, the one exception to the
alternating labels is the last visited child $b_\ell$, whose $\nothing_{st}$ or $\nothing_{ts}$ label
needs to match that of its parent $b$.
%The direction, $L$ or $R$,
%is determined by the spiral's cycling direction when it enters $b_\ell$
%(counterclockwise if there are an odd number of back children and clockwise
%if there are an even number).
After visiting $b_\ell$, the exiting spiral follows the entering spiral in reverse to $t$
as in Section~\ref{sec:eps-recursive}, %which completes
thus completing the visit of $b$.


\subsection{The Delta-Unfolding Algorithm for Extrusions}
\label{sec:analysis}

%\xxx[JOR]{This is a formidably long, undifferentiated section!
%Needs structuring.  And it is the heart of the new contribution.}
%Having detailed the construction of a path $\xi$ that
%visits any specified front- or back-child last,
%we next \textcolor{red}{summarize the new algorithm and analyze the
%refinement level.}
%explain how a variation
%\xxx[JOR]{How is it a ``variation''? Never made clear...}
%of heavy-path decomposition reduces the
%refinement to quadratic complexity.
%In a heavy-path decomposition~\cite{Sleator-Tarjan-1983},
%\xxx[JOR[]{Ah!  This needs to be earlier!}
%each node $v$ in a tree is
%assigned a weight $n(v)$, which is the number of descendants in its
%subtree, including itself.  An edge from parent $p$ to child $c$ is
%\emph{heavy} if $n(c) > \frac{1}{2}n(p)$, and \emph{light} otherwise. We say a child
%$c$ is \emph{heavy} if the edge between $c$ and its parent is heavy. Note that
%a node can have at most one heavy child.
What we call the {\em delta-unfolding} algorithm is
a modified version of the epsilon-unfolding algorithm, % such that for
which requires that at each node $b$ in $T_U$
with a heavy child, the spiral $\xi$ visits the heavy child last.
Specifically, if the heavy child is a front child, then $\xi$ follows the
path described in Section~\ref{sec:heavyfront}; if %it
the heavy child is a back child, then $\xi$ follows the
path described in Section~\ref{sec:heavyback}.
%\xxx[JOR]{This is the key, and you established earlier it is possible,
%  but without explaining the point.}
If $b$ has no heavy child, then its children are visited in the
epsilon-unfolding order (Section~\ref{sec:eps-recursive}).
%
All remaining steps of the delta-unfolding algorithm for extrusions---the
thickening of $\xi$, the unfolding of $\xi$ as a staircase in the plane,
and the partitioning and hanging of the frontward and rearward faces from the
flattened staircase---are the same as for epsilon-unfolding.

\subsection{Refinement Analysis}

We now turn to analyzing the refinement for extrusions. The path taken by $\xi$
on a band is composed of a series of
% $x$-, $y$- and $z$-
axis-parallel segments.
%\xxx[JOR]{Later the distinction between $x$, $y$, and $z$ is
%  lost---never mentioned again.  So is it appropriate/necessary to distinguish
%  them here?}
We determine an asymptotic upper bound on the number
of such segments on any band face,
because this is an asymptotic upper bound on the total
number of cuts on a grid face in the unfolding. We compute this by bounding the number
of segments on any top face, as the number of segments on all four faces of a
band is asymptotically bounded by the number of segments on its top face.

Define the {\em first visit} of $\xi$ to a band $b$ to begin
when $\xi$ {\em first} enters $b$ at point $s$, includes the recursive visiting of
$b$'s children, and ends when it exits $b$ at point $t$.
%, never to
%return. \xxx[JOR]{Right? :-)}
Band
$b$ and the bands in its subtree may be revisited by $\xi$ many times during
subsequent retracings, but each of these retracings merely follows the path traced
during the first visit to $b$.
Let $R(n(b))$ be an asymptotic upper bound on the number of segments that
$\xi$'s first visit to $b$
induces on a top face of any band in the unfolding subtree rooted at $b$.
Then a bound on the number of
 segments on any top face in $b$'s subtree induced by $\xi$ (in its entirety) is $R(n(b))$
multiplied by the total number of times $\xi$ visits $b$.
%
We now establish three properties of $\xi$'s first visit to $b$:
\begin{enumerate}[(i)]
\item $\xi$ induces at most $O(n(b))$  segments on $b$'s top face;
\item the light children of $b$ are each visited at most four times; and
\item if $b$ has a heavy child, the heavy child is visited only once.
\end{enumerate}

For (i), the worst case occurs when
$b$ has $O(n(b))$ children and a heavy front child $b_\ell$.
In this case, the
alternating paths of $b$'s entering spiral $\xi_e(b)$
that have it visit each front child (excluding $b_\ell$) may induce
$O(n(b))$  segments on $b$'s top face, and similarly for the alternating paths to each
back child.
Then $b$'s return spiral $\xi_r(b)$ retraces these alternating paths up to the point
that it reaches $b_\ell$, which
at most doubles the number of  segments.
After visiting  $b_\ell$,
the exiting spiral $\xi_x(b)$ retraces the path $\xi_r(b)$ and then the path
$\xi_e(b)$ in reverse back to point $t$ on $b$, which again
at most doubles the number of  segments
on $b$. Thus the total number of  segments is $O(n(b))$.

For~(ii), the maximum visits to light children occur when
$b$ has a heavy front child. In this case,
% and~(iii), observe that
$\xi_e(b)$ visits each light child once.
% with the exception of one
%back child, call it $b_\omega$, whose entering point marks the end of $\xi_e(b)$.
%$b_\omega$ is visited (once), and
Then $\xi_r(b)$
%begins at the exiting point of $b_\omega$. $\xi_r(b)$
visits each light child at most once on its way to the heavy front child. After visiting the heavy
front child, $\xi_x(b)$ retraces
$\xi_r(b)$
%back to $b_\omega$, revisits $b_\omega$,
and then retraces
$\xi_e(b)$ to the entering point of $b$, thus visiting each light child
at most twice more. Therefore,
each light child is visited at most four times.
%

For~(iii), if $b$ has a heavy front child, then the path traversed by $\xi$
(detailed in Section~\ref{sec:heavyfront}) immediately establishes that the heavy front
child is visited only once. Similarly, if $b$ has a heavy back child, the path detailed
in Section~\ref{sec:heavyback} establishes that %it is only visited once.}
the heavy back child is visited exactly once.
%
%Let $b_w$ be the last visited back child whose entering point marks
%the termination of $\xi_e(b)$.
%\xxx[JOR]{Why $\_w$?  I can see $\_\ell$, but ... ?
%(Is your $w$ hinting at $\omega$?)
%I suggest you go Biblical:  ``I am the $\_\alpha$ and the $\_\omega$...'' :-)}
%By definition of $\xi_e(b)$ and $\xi_r(b)$, they do not
%include visits to $b_w$. %so
%(Recall that $\xi_e(b)$ extends from $s$ to the
%entering point $s_w$ of $b_w$, and $\xi_r(b)$ extends from the exiting point $t_w$
%of $b_w$ to the entering point $s_\ell$ of $b_\ell$.)
%Thus we observe separately\xxx[JOR]{???} that, if $b$
%has a heavy back child or if $b$ has no heavy child, then
%$b_w$ is visited only once between $\xi_e(b)$ and $\xi_x(b)$. (There is no return spiral in
%these cases, and if $b$ has a heavy back child, then the visit order of $\xi_e(b)$ ensures
%that $b_\ell = b_w$.)
%If $b_w$ is not heavy and there is a heavy front child, then
%$b_w$ is visited twice---once between $\xi_e(b)$ and $\xi_r(b)$ and
%then again by $\xi_x(b)$.
%When heavy child $b_\ell$ is a front child, observe that it is visited just once
%between $\xi_r(b)$ and $\xi_x(b)$.

Properties (i), (ii) and (iii) established above imply that $R(n(b))$ is determined
by the larger of three quantities:
\begin{enumerate}[(a)]
\item the number of  segments on $b$'s top face induced during $\xi$'s
first visit to $b$;
\item $4\max_{i=1\dots k} R(n(b_i))$, where $b_1, b_2,\dots b_k$ are $b$'s
light
%front and back
children;
%, not including its heavy child $b_\ell$ if it has
%one; and
\item $R(n(b_\ell))$, where $b_\ell$ is $b$'s heavy child, if it has one.
%it has a heavy child.
\end{enumerate}
A multiplier of four is necessary in case~(b) because light children may be visited up to four times during $b$'s first visit; no multiplier is
necessary for the heavy child~(c) because it is visited only once. For the base case,
$R(1) = c$, for some constant $c > 1$, because the first visit of $\xi$ to
a leaf node band (as described in Section~\ref{sec:basecase}) induces a constant
number of  segments.
%\xxx[JOR]{To explain a frequent replacement:
%I prefer ``because'' over ``since,'' as the latter can be
%  interpreted as involving time (and ideally should be so reserved).
%But it becomes boringly repetitive to replace
%  \emph{every} instance...}
And in general,
%
\begin{eqnarray*}
 R(n(b)) & = & \max \left\{O(n(b)), ~4\max_{i=1\dots k} R(n(b_i)) , ~R(n(b_\ell))\right\} \\
            &  \leq & \max \left\{O(n(b), ~4\max_{i=1\dots k} R\left( {\textstyle \frac{1}{2}} n(b) \right), ~R(n(b)-1) \right\} \\
            &  = & \max \left\{O(n(b), ~4R\left( {\textstyle \frac{1}{2}}n(b) \right), ~R(n(b)-1) \right\}
\end{eqnarray*}
%
noting that the light children's subtrees contain at most $\frac{1}{2}n(b)$ nodes,
and the heavy child's subtree contains at most $n(b)-1$ nodes. It is
straightforward to verify by induction that $R(n(b)) = O(n(b)^2)$.
Applying this to the root $r$ of $T_U$ with $n = n(r)$ nodes
and noting that $\xi$ visits $r$ only once in the delta-unfolding
algorithm,
%\xxx[JOR]{I think the term ``delta-unfolding'' has not yet been
%  defined.
%Earlier on it should be mentioned that ``We will now modify the
%epsilon-unfolding algorithm to what we call a \emph{delta-unfolding} algorithm.}
yields a maximum of $O(n^2)$  parallel segments on any top face.

This also bounds the number of cuts on any grid face in the unfolding.
Specifically, in the thickening step $\xi$ expands in the $+y$ and $-y$
direction so as to cover the entire band, but this does not asymptotically
increase its number of edges.
After the thickening, disjoint sections of
$\xi$ run along the entirety of both band rims. In the partitioning
step, the disjoint sections along the top rim edges
induce the division of the frontward and rearward faces into strips;
i.e., each disjoint section delimits the vertical strip beneath it. Because $O(n^2)$
bounds the number of disjoint sections along the top edge, it also bounds the number of strips
a frontward/rearward face is partitioned into.

\subsubsection{A worst case refinement example.}
%
A simple example establishes that the bound $O(n^2)$ is tight: a
polyhedron with $n = 2^{h+1}-1$ blocks,
%\xxx[JOR]{Blocks?  See earlier comment.}
whose unfolding tree $T_U$ is a perfect
%\xxx[JOR]{balanced? Not sure of
%the preferred notation.}
binary tree of height $h$ (i.e., each internal node has two children, and all
leaves are at the same level).
There are no heavy nodes in $T_U$, and the number of cuts in a visit of
the root is given by the recurrence relation
$$
R(n)=4R((n-1)/2) = 4^{h}R(1) = (n+1)^2R(1)/4
\;,
$$
because
$$
4^h = 4^{\log_2(n+1) - 1} = 2^{\log_2(n+1)^2} /4 = (n+1)^2/4
\;.
$$
And since $R(1) = c$, for some constant $c$, it follows that $R(n) =
O(n^2)$,
establishing our claim.

\section{Delta-Unfolding of Genus-Zero Orthogonal Polyhedra}
\label{Delta-Unfolding of Genus-Zero Orthogonal Polyhedra}

The delta-unfolding algorithm and its refinement analysis
generalizes to all genus-zero orthogonal polyhedra in the same
way the epsilon-unfolding algorithm does, so we summarize the idea here and refer the
reader to~\cite{Damian-Flatland-O'Rourke-2007-epsilon} for details. Instead of partitioning $P$ into blocks, the general algorithm
partitions $P$ into slabs as defined in Section~\ref{sec:overview}.
It then creates an unfolding tree, $T_U$, where each node corresponds to a band surrounding a slab.
Each parent-child arc in $T_U$ corresponds to a $z$-beam, which is a vertical strip from a frontward or rearward face connecting the parent's rim to the child's rim.
For a parent band $b$, its front (back) children are those
whose $z$-beams connect to $b$'s front (back) rim.
%which are located where the $z$-beam to $b$'s parent connects with $b$'s front rim.

The spiral $\xi$ enters and exits $b$ at points $s$ and $t$
located at the intersection between $b$'s front rim and the $z$-beam
connecting $b$ to its parent.
Observe that there is a natural cyclic ordering of $b$'s front (back) children that is determined by their
$z$-beam connections around $b$'s front (back) rim.  Using this cyclic ordering, it
is straightforward to generalize the paths that $\xi$ follows to reach the
front and back children, described in Sections~\ref{sec:heavyfront} and~\ref{sec:heavyback}.
See for example Figure~\ref{fig:genUnfEx} that shows a band %cut (in the $y$ direction)
with its faces flattened in the plane (the lighter color marks top/bottom faces, and
the darker color marks right/left faces). Also depicted are
the $z$-beam connections (flattened into the plane) and the path $\xi_e(b)$  follows
to visit the children, assuming $b_\ell$ is a heavy child. Observe that the path is
the same as in Figure~\ref{fig:unfex}, except that it extends across multiple band faces.
When $\xi$ visits a child, it moves from $b$ to
the connecting $z$-beam and travels vertically (in 3D) along the $z$-beam to reach the child;
when it exits the child it travels along the $z$-beam back to $b$.
In the unfolded staircase, the portion
of $\xi$ on the $z$-beam corresponds to a vertical riser. Thickening $\xi$ is done
as in the case of %the same as for
extrusions. The partitioning of the
forwards and rearwards faces is also %the same, except that
done as in the case of extrusions, but
in addition to shooting illuminating rays down from top rim edges, bottom rim edges that are not hit by these rays must
themselves shoot rays upward to illuminate portions of faces not illuminated by
the top edges. %Then the partitioned pieces
The face pieces resulting from this partitioning method
are hung from the staircase as described in Section~\ref{sec:frontback}. %before.}
%\xxx[JOR]{I apologize for this, but I feel a need for some
%  justification here.  It really is a HUGE leap from extrusions to
%  general orthogonal polyhedra.  Perhaps a few sentences, or a
%  paragraph?
%The ``thus'' following is just not convincing:}
%Thus we achieve quadratic refinement.
%that $O(n^2)$ bounds the number of cuts made on any band face,
%and thus we
%achieve quadratic refinement.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure Begin
\begin{figure}[htbp]
\centering
\includegraphics[width=0.8\linewidth]{genUnfEx}
%\fbox{genUnfEx}
\caption{Band $b$ of a slab, cut and laid flat with top/bottom faces light gray and right/left
faces dark gray. $z$-beam connections to $b$'s parent, children $b_1 \dots b_9$, and child $b_\ell$
are marked along the front and back rim. The path that $\xi_e(b)$ follows
when $b_\ell$ is heavy is depicted.}
\label{fig:genUnfEx}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure End

The $O(n^2)$ upper bound on the level of grid refinement for extrusions also applies to general orthogonal polyhedra by the following argument. In the case of extrusions, for any block $b$ with children, $\xi$ makes turns only
on $b$'s top face, because all access to the children is
from the top face; it makes no turns on the other three faces of $b$.
Therefore, we analyze the
number of segments (each corresponding to a turn) on the top face. For a band $b$
of an arbitrary orthogonal polyhedra, $\xi$ visits $b$'s children in the same manner as for
an extrusion, except that the turns made to access the children are made
on whatever top or bottom face has the connecting $z$-beam, as in Figure~\ref{fig:genUnfEx}. In particular, for a band $b$ with a given number
of front and back children, the same number of turns are made, whether
$b$ surrounds a block of an extrusion or a slab of a arbitrary orthogonal polyhedron.
In terms of maximum refinement, the worst case occurs when all the turns are
concentrated on a single face, which is exactly the situation handled by our upper bound
analysis in the case of extrusions.
%what was analyzed in the case of extrusions.}

\section{Conclusion}
We present modifications to the %We modified the
epsilon-unfolding algorithm from~\cite{Damian-Flatland-O'Rourke-2007-epsilon} that reduce the level of grid
refinement necessary to grid-unfold any
%which unfolds any
genus-zero orthogonal polyhedron from exponential to quadratic.
%using potentially exponential refinement
%of the vertex grid, to our ``delta-unfolding'' algorithm, which follows
%the same general plan
%and achieves the same result,
%but with only
%quadratic refinement.
%
The next natural step is to seek a refined grid edge-unfolding of all genus-zero
orthogonal polyhedra that requires subquadratic refinement of the
grid faces, to date only achieved for highly restricted classes of
orthogonal polyhedra~\cite{Biedl-Demaine-Demaine-Lubiw-Overmars-O'Rourke-Robbins-Whitesides-1998,Damian-Flatland-O'Rourke-2008-manhattan,Damian-Meijer-2004-orthostacks}.
It is unlikely
that the technique used in this paper could be extended to produce such an unfolding, due
to the backtracking nature of our recursive unfolding algorithm. However, our preliminary
investigations embolden us
%\xxx[JOR]{:-)}
to conjecture that a constant refinement of the vertex grid
suffices to grid-unfold all orthogonal polyhedra.
%Such a result would
%constitute a
%significant step
%toward our final objective, which is to show that no refinement of the vertex grid is
%necessary to unfold any given orthogonal polyhedron.
%\xxx[JOR]{Even optimistic \emph{Joe} wouldn't conjecture this!}

\paragraph{Acknowledgement.} The authors would like to thank Joseph O'Rourke for his careful 
reading and helpful suggestions.

\bibliographystyle{alpha}
\bibliography{unfolding}

\end{document}

unfolding.bbl
\newcommand{\etalchar}[1]{$^{#1}$}
\begin{thebibliography}{DFMO05}

\bibitem[ABC{\etalchar{+}}10]{Aloupis-Bose-Collette-Demaine-Demaine-Douieb-Dujmovic-Iacono-Langerman-Morin-2010}
Greg Aloupis, Prosenjit~K. Bose, Sebastien Collette, Erik~D. Demaine, Martin~L.
  Demaine, Karim Douieb, Vida Dujmovi\'c, John Iacono, Stefan Langerman, and
  Pat Morin.
\newblock Common unfoldings of polyominoes and polycube.
\newblock In {\em Revised Papers from the China-Japan Joint Conference on
  Computational Geometry, Graphs and Applications}, volume 7033 of {\em Lecture
  Notes in Computer Science}, pages 44--54, Dalian, China, November 2010.

\bibitem[AD11]{Abel-Demaine-2011}
Zachary Abel and Erik~D. Demaine.
\newblock Edge-unfolding orthogonal polyhedra is strongly np-complete.
\newblock In {\em Proceedings of the 23rd Canadian Conference on Computational
  Geometry}, Toronto, Canada, August 2011.

\bibitem[BDD{\etalchar{+}}98]{Biedl-Demaine-Demaine-Lubiw-Overmars-O'Rourke-Robbins-Whitesides-1998}
Therese Biedl, Erik Demaine, Martin Demaine, Anna Lubiw, Mark Overmars, Joseph
  O'Rourke, Steve Robbins, and Sue Whitesides.
\newblock Unfolding some classes of orthogonal polyhedra.
\newblock In {\em Proceedings of the 10th Canadian Conference on Computational
  Geometry}, Montr\'eal, Canada, August 1998.

\bibitem[BDE{\etalchar{+}}03]{Bern-Demaine-Eppstein-Kuo-Mantler-Snoeyink-2003}
Marshall Bern, Erik~D. Demaine, David Eppstein, Eric Kuo, Andrea Mantler, and
  Jack Snoeyink.
\newblock Ununfoldable polyhedra with convex faces.
\newblock {\em Computational Geometry: Theory and Applications}, 24(2):51--62,
  February 2003.

\bibitem[DFMO05]{Damian-Flatland-Meijer-O'Rourke-2005-orthotrees}
Mirela Damian, Robin Flatland, Henk Meijer, and Joseph O'Rourke.
\newblock Unfolding well-separated orthotrees.
\newblock In {\em Abstracts from the 15th Annual Fall Workshop on Computational
  Geometry}, Philadelphia, PA, November 2005.

\bibitem[DFO07]{Damian-Flatland-O'Rourke-2007-epsilon}
Mirela Damian, Robin Flatland, and Joseph O'Rourke.
\newblock Epsilon-unfolding orthogonal polyhedra.
\newblock {\em Graphs and Combinatorics}, 23(1):179--194, 2007.

\bibitem[DFO08]{Damian-Flatland-O'Rourke-2008-manhattan}
Mirela Damian, Robin Flatland, and Joseph O'Rourke.
\newblock Unfolding {M}anhattan towers.
\newblock {\em Computational Geometry: Theory and Applications}, 40:102--114,
  2008.

\bibitem[DM04]{Damian-Meijer-2004-orthostacks}
Mirela Damian and Henk Meijer.
\newblock Edge-unfolding orthostacks with orthogonally convex slabs.
\newblock In {\em Abstracts from the 14th Annual Fall Workshop on Computational
  Geometry}, pages 20--21, Cambridge, MA, November 2004.
\newblock \url{http://cgw2004.csail.mit.edu/talks/34.ps}.

\bibitem[DO05]{Demaine-O'Rourke-2005}
Erik~D. Demaine and Joseph O'Rourke.
\newblock A survey of folding and unfolding in computational geometry.
\newblock In Jacob~E. Goodman, J\'anos Pach, and Emo Welzl, editors, {\em
  Discrete and Computational Geometry}, Mathematical Sciences Research
  Institute Publications, pages 167--211. Cambridge University Press, 2005.

\bibitem[DO07]{Demaine-O'Rourke-2007}
Erik~D. Demaine and Joseph O'Rourke.
\newblock {\em Geometric Folding Algorithms: Linkages, Origami, Polyhedra}.
\newblock Cambridge University Press, July 2007.

\bibitem[O'R08]{O'Rourke-2008-orthosurvey}
Joseph O'Rourke.
\newblock Unfolding orthogonal polyhedra.
\newblock In J.~E. Goodman, J.~Pach, and R.~Pollack, editors, {\em Surveys on
  Discrete and Computational Geometry: Twenty Years Later}, pages 231--255.
  American Mathematical Society, 2008.

\bibitem[ST83]{Sleator-Tarjan-1983}
Daniel~D. Sleator and Robert~Endre Tarjan.
\newblock A data structure for dynamic trees.
\newblock {\em Journal of Computer and System Sciences}, 24(3):362--391, June
  1983.

\end{thebibliography}
