DIMACS TR: 94-43

Authors: R.L. Graham, B.D. Lubachevsky

PLEASE NOTE:  This abstract is in LATEX.

\documentstyle[11pt]{article}

\setlength{\textwidth}{6.2in}
\setlength{\textheight}{9in}
\setlength{\oddsidemargin}{.2in}
\setlength{\topmargin}{-0.25in}
\setlength{\headheight}{0in}

\newcommand{\la}{\lambda}
\newcommand{\af}{\alpha}
\newcommand{\lt}{\left(}
\newcommand{\rt}{\right)}
\newcommand{\df}{\displaystyle\frac}
\newcommand{\dis}{\displaystyle}
\newcommand{\ga}{\gamma}
\newcommand{\ep}{\epsilon}
\newcommand{\Om}{\Omega}
\newcommand{\dd}{\ldots}
\newcommand{\In}{\infty}
\newcommand{\lf}{\lfloor}
\newcommand{\rf}{\rfloor}
\newcommand{\lc}{\lceil}
\newcommand{\rc}{\rceil}
\newcommand{\beql}[1]{\begin{equation}\label{#1}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\EE}{{\Bbb E}}

\makeatletter
\@addtoreset{figure}{section}
\def\thefigure{\thesection.\@arabic\c@figure}
\makeatother

\thispagestyle{empty}
\begin{document}
\begin{center}
{\Large {\bf Dense Packings of Equal Disks in an Equilateral \\
\vspace{.1\baselineskip}
Triangle: From 22 to 34 and Beyond}} \\
\vspace{\baselineskip}
{\em R. L. Graham} \\
{\em B. D. Lubachevsky} \\
\vspace{.25\baselineskip}
AT\&T Bell Laboratories, \\
Murray Hill, New Jersey 07974 \\
\vspace{1.5\baselineskip}
{\bf ABSTRACT}
\vspace{.5\baselineskip}
\end{center}

Previously published packings of equal disks in an equilateral
triangle have dealt with up to 21 disks.
We use a new discrete-event simulation algorithm to produce
packings for up to 34 disks.
For each $n$ in the range $22 \le n \le 34$ we present what we believe
to be the densest possible packing of $n$ equal disks in an
equilateral triangle.
For these $n$ we also list the second, 
often the third and sometimes the fourth best packings 
among those that we found.
In each case, the structure of the packing implies that the minimum
distance $d(n)$ between disk centers is the root of polynomial
$P_n$ with integer coefficients.
In most cases we do not explicitly compute $P_n$ 
but in all cases we do compute and report $d(n)$ 
to 15 significant decimal digits.

Disk packings in equilateral triangles differ 
>from those in squares or circles in that for triangles 
there are an infinite number of values of $n$ 
for which the exact value of $d(n)$ is known,
namely, when $n$ is of the form $\Delta (k) := \frac{k(k+1)}{2}$.
It has also been conjectured that $d(n-1) = d(n)$ in this case.
Based on our computations, we present conjectured optimal packings
for seven other infinite classes of $n$, namely
\begin{eqnarray*}
n & = & \Delta (2k) +1,~\Delta (2k+1) +1,
\Delta (k+2) -2 , ~ \Delta (2k+3) -3, ~ \\
&& \Delta (3k+1)+2 ,
~ 4 \Delta (k), ~~\mbox{and}~~
2 \Delta (k+1) + 2 \Delta (k) -1 ~.
\end{eqnarray*}
We also report the best packings we found 
for other values of $n$ in these forms 
which are larger than 34, namely, 
$n=37$, 40, 42, 43, 46, 49, 56, 57, 60, 63, 67, 71, 79, 84, 92, 93, 106, 112, 12
1, and 254,
and also for $n=58$, 95, 108, 175, 255, 256, 258, and 260.
We say that an infinite class of packings of $n$ disks,
$n=n(1), n(2),...n(k),...$, 
is {\em tight }, if
[$1/d(n(k)+1) - 1/d(n(k))$] is
bounded away from zero as $k$ goes to infinity.
We conjecture that some of our infinite classes are tight,
others are not tight, and that there are infinitely many 
tight classes.
\end{document}

DIMACS Home Page