A Note on Objects Built From Bricks\\without Corners
% Mirela Damian% \thanks{Department of Computer Science
Villanova
PA 19085
Joseph O'Rourke% \thanks{Department of Computer Science
Smith College
Northampton
MA 01063
We report a small advance on a question raised by Robertson, Schweitzer, and Wagon in~\cite{rsw-bo-02}. They constructed a genus-13 polyhedron built from bricks without corners, and asked whether every genus-0 such polyhedron must have a corner. A brick is a parallelopiped, and a corner is a brick of degree three or less in the brick graph. We describe a genus-3 polyhedron built from bricks with no corner, narrowing the genus gap.
NoCorners.tex
\documentclass[]{article}  
\usepackage{url}
\usepackage{graphicx}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{latexsym}

%\input{/home1/orourke/tex/mac}
\input{mac}

\withcomplaints

\def\a{{\alpha}}
\def\g{{\gamma}}
\def\e{{\epsilon}}
\def\G{{\Gamma}}
\def\C{{\mathcal C}}
\def\int{{\mathrm{int}}}


% Blackboard R for real numbers, S for sphere (\S taken someplace, so \Sph).
\newcommand\R{\mathbb{R}}
%\newcommand\Sph{\mathbb{S}}

\setlength{\oddsidemargin}{0.2in}
\setlength{\textwidth}{6.2in}

\begin{document}

\title{A Note on Objects Built From Bricks\\without Corners}

\author{%
Mirela Damian%
   \thanks{Department of Computer Science, Villanova University, Villanova,
PA 19085, USA.
   \protect\url{mirela.damian@villanova.edu}.}
\and
Joseph O'Rourke%
    \thanks{Department of Computer Science, Smith College, Northampton, MA
      01063, USA.
      \protect\url{orourke@cs.smith.edu}.
       Supported by NSF Distinguished Teaching Scholars award
       DUE-0123154.}
}
\maketitle

\begin{abstract}
We report a small advance on a question raised
by Robertson, Schweitzer, and Wagon
in~\cite{rsw-bo-02}.
They constructed a genus-13 polyhedron built from bricks without
corners, and asked whether every genus-0 such polyhedron
must have a corner.  
A \emph{brick} is a parallelopiped, and
a \emph{corner} is a brick of degree three or less
in the brick graph.
We describe a genus-3 polyhedron built from bricks with no corner,
narrowing the genus gap.
\end{abstract}


\section{Introduction}
Sibley and Wagon~\cite{sw-rpt3c-00}
proved that any collection of paralleograms glued whole-edge to
whole-edge must have at least one ``elbow'':  
a parallelogram with at most two neighbors.
This enabled them to prove that such tilings are
$3$-colorable.
The analogous question in 3D is~\cite{w-mrfch-02,do-op02-03}:
Must every object built from paraellopipeds (henceforth,
\emph{bricks}) have at least one corner, a brick with
at most three neighbors?
The bricks must be \emph{properly joined}:
each pair 
is either disjoint, or intersects either in a
single point,
a single whole edge of each, or a single whole face of each.
Two bricks in a collection are \emph{adjacent} if they share a single whole face.
Define the \emph{brick graph} of a collection of bricks to have
a node for each brick, and an arc for each pair of adjacent bricks.
The question is whether there must exist a node of degree $\le 3$
in the brick graph.
If so, $4$-colorability could be established.

The answer is {\sc no}: Robertson, Schweitzer, and Wagon
found a polyhedron with no corner.
This settled one question but raised another:  Might this be
true for a topological \emph{ball}, i.e., an object of genus~0
(their Question~1)?
Their example has a high genus; we show below its genus is $13$.
The main purpose of this note is to describe another example
that has genus~3.

\section{The Buttressed Octahedron}
Fig.~\figref{stan.oct} shows the $52$-brick
example from~\cite{rsw-bo-02}, in two views.
As shown, it has corners, but when each brick is partitioned
into eight sub-bricks from its center, it is an object
built from bricks with no corners.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure Begin
\begin{figure}[htbp]
\centering
\includegraphics[width=0.95\linewidth]{stan.oct.eps}
%\fbox{stan.oct.eps}
\caption{An object with no corners (when refined).
[Fig.~1 from \protect\cite{rsw-bo-02}, by permission.]
}
%Permission granted by Stan, 14 July 2003.
\figlab{stan.oct}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure End

The authors did not report its genus.
We compute the genus from
the Euler characteristic $V-E+F=\chi$, which is
equal to $2 - 2g$, where $g$ is the genus.
This computation is performed on the unrefined object in the figure;
because $\chi$ is a topological invariant, 
it is unaltered by refinement/splitting.
The calculations are shown in Table~1. %\tabref{Euler.Stan}.

\begin{table}[htbp]
\begin{center}
\begin{tabular}{| l | c | c | c |}
	\hline
Pieces
	& $V$
	& $E$
	& $F$
	\\ \hline \hline

ring ($4$ quarters)
	& $4 \times 20 = 80$
	& $4 \times 40 = 160$
	& $4 \times 16 =64$
	\\ \hline
arch $(2)$
	& $2 \times 30 = 60$
	& $2 \times 66 = 132$
	& $2 \times 32 = 64$
	\\ \hline
buttress $(8)$
	& $0$
	& $8 \times 4 = 32$
	& $8 \times 4 = 32$
	\\ \hline \hline
sum
	& $140$
	& $324$
	& $160$
	\\ \hline

\end{tabular}
\caption{Euler characteristic calculations
$V-E+F=-24$.}
\end{center}
\tablab{Euler.Stan}
\end{table}

\begin{eqnarray*}
%V-E+F & = & 2 - 2 g\\
V-E+F & = & 140 - 324 + 160 \; = \; 2 - 2g\\
% & = & -24\\
% 2 - 2 g & = & -24\\
 g & = & 13
\end{eqnarray*}

\section{The ZZ-Object}
The overall design of our new example is shown in
Fig.~\figref{ZZ.int}.
It consists of two {\tt Z}-shaped paths
connecting four cubes.
Each of the long connectors has no corner when split lengthwise into four
bricks.  Similarly, the four cubes have no corners when split into eight cubes.
Prior to splitting, the object consists of only $10$ bricks.
However, as is evident from the figure, it is self-intersecting.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure Begin
\begin{figure}[htbp]
\centering
\includegraphics[width=0.75\linewidth]{ZZ.int.eps}
%\fbox{ZZ.int.eps}
\caption{A self-intersecting object with no corners (after refinement).}
\figlab{ZZ.int}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure End
In the figure, the centers of the four cubes are staggered 
at these coordinates:
\begin{eqnarray*}
& & ( 30, 40, 50 ) \\
& & ( 60, 10, 40 ) \\
& & ( 10, 20, 30 ) \\
& & ( 55, 30, 10 )
\end{eqnarray*}
The design of the object relies on this observation:
If it can be arranged that every brick has two opposite faces
covered by other bricks, then splitting will render it cornerless,
with every sub-brick with $\le 2$ exposed faces, and so of degree $\ge 4$.

The self-intersection can be removed by zig-zagging one of
the {\tt Z}s.
The resulting object of $14$ bricks is shown in 
Fig.~\figref{ZZ.noint}, in two views.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure Begin
\begin{figure}[htbp]
\centering
\includegraphics[width=0.75\linewidth]{ZZ.noint.a.eps}
\includegraphics[width=0.75\linewidth]{ZZ.noint.b.eps}
\caption{A non-self-intersecting object of genus $3$ with no corners (after refinement).}
\figlab{ZZ.noint}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure End



We again compute the Euler characteristic $\chi$.
Because of its topological invariance, we compute it for
the simpler object in Fig.~\figref{ZZ.int}, which
has the same
genus as the object in Fig.~\figref{ZZ.noint} .  We count all vertices as part of the cubes.
All $12$ edges of every cube are exposed, but only $3$ faces of each.
Each of the  $6$ connecting bricks contributes $4$ edges and $4$ faces.
The calculations are shown in Table~2. %\tabref{Euler.ZZ}.

\begin{table}[htbp]
\begin{center}
\begin{tabular}{| l | c | c | c |}
	\hline
Pieces
	& $V$
	& $E$
	& $F$
	\\ \hline \hline

cubes $(4)$
	& $4 \times 8 = 32$
	& $4 \times 12 = 48$
	& $4 \times 3 =12$
	\\ \hline
connectors $(6)$
	& $0$
	& $6 \times 4 = 24$
	& $6 \times 4 = 24$
	\\ \hline \hline
sum
	& $32$
	& $72$
	& $36$
	\\ \hline

\end{tabular}
\caption{Euler characteristic calculations
$V-E+F=-4$.}
\end{center}
\tablab{Euler.ZZ}
\end{table}

\begin{eqnarray*}
%V-E+F & = & 2 - 2 g\\
V-E+F & = & 32 -72 + 36 \; = \; 2 - 2 g\\
% & = & -4\\
% 2 - 2 g & = & -4\\
 g & = & 3
\end{eqnarray*}

\section{Conclusion}
We have constructed a $14$-brick, genus-$3$ object, 
which when refined by splitting,
has no corners.
The question remains whether there exists an object %built with bricks
without corners of smaller genus: $2$, $1$, or $0$.  
We conjecture that all brick objects of genus~$0$ must have a corner.
This gains some support from the work in~\cite{go-cobb-03}
which shows that one class of topological balls always has
at least four corners. %, and so is $4$-colorable.


\paragraph{Acknowledgements.}
We thank
Sasha Berkoff,
Asten Buckles,
Jessie McCartney,
and Shawna King for assisting in the preparation of Figs.~2 and~3.

\bibliographystyle{alpha}
\bibliography{/home1/orourke/bib/geom/geom}

\end{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{df}
\end{df}


\begin{lemma}
\lemlab{X}
\end{lemma}
\begin{pf}
\end{pf}

\begin{enumerate}
\end{enumerate}

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



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure Begin
\begin{figure}[htbp]
\centering
\begin{minipage}[c]{0.5\linewidth}
\centering
\includegraphics[width=\linewidth]{ZZ.noint.a.eps}
\end{minipage}
\begin{minipage}[c]{0.5\linewidth}
\centering
\includegraphics[width=\linewidth]{ZZ.noint.b.eps}
\end{minipage}
\caption{A non-self-intersecting object of genus $3$ with no corners (after refinement).}
\figlab{ZZ.noint}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure End

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

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

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


NoCorners.bbl
\begin{thebibliography}{RSW02}

\bibitem[DO03]{do-op02-03}
Erik~D. Demaine and Joseph O'Rourke.
\newblock Open problems from {CCCG} 2002.
\newblock In {\em Proc. 15th Canad. Conf. Comput. Geom.}, 2003.
\newblock To appear. arXiv cs.CG/0212050.
  \protect\url{http://arXiv.org/abs/cs/0212050/}.

\bibitem[GO03]{go-cobb-03}
Suzanne Gallagher and Joseph O'Rourke.
\newblock Coloring objects built from bricks.
\newblock In {\em Proc. 15th Canad. Conf. Comput. Geom.}, 2003.
\newblock To appear.

\bibitem[RSW02]{rsw-bo-02}
Lew Robertson, Michael Schweitzer, and Stan Wagon.
\newblock A buttressed octahedron.
\newblock {\em Geomcombinatorics}, 11(4):119--124, 2002.

\bibitem[SW00]{sw-rpt3c-00}
Thomas Sibley and Stan Wagon.
\newblock Rhombic {P}enrose tilings can be 3-colored.
\newblock {\em American Mathematics Monthly}, 106:251--253, 2000.

\bibitem[Wag02]{w-mrfch-02}
Stan Wagon.
\newblock A machine resolution of a four-color hoax.
\newblock In {\em Proc. 14th Canad. Conf. Comput. Geom.}, pages 181--193,
  August 2002.

\end{thebibliography}
