% The following is for LaTeX2e.
\documentclass[11pt,twocolumn]{article}
\usepackage{samplesty} % Includes the sample style file
\usepackage{epsfig}

% The following is for LaTeX 2.09.
% \documentstyle[11pt,twocolumn,samplesty,epsfig]{article}

\begin{document}

\title{Disk Packing for the Estimation of the Size of a Wire Bundle}
\author{Kokichi Sugihara\\University of Tokyo\\{\tt
sugihara@mist.i.u-tokyo.ac.jp} \and Deok-Soo Kim \\ Hanyang
University \\ {\tt dskim@hanyang.ac.kr} }
\date{}
\maketitle

\begin{abstract}
A heuristic method for packing disks in a circle is constructed, and
is applied to the estimation of the sizes of holes through
which given sets of
electric wires are to pass.
In the proposed method, a
sufficiently large circle is initially constructed, and it is shrunk
step by step while keeping all the disks inside.  For this purpose
a Voronoi diagram for circles is used.  Computational experiments
show the validity and the efficiency of the method.

\vspace*{5mm}
\noindent
{\bf Key words:}  circle packing, circle Voronoi diagram, wire bundling,
bundle size, automobile industry
\end{abstract}

\section{Introduction} %1

Modern intelligent cars contain many electric systems.  For example,
a car has many sensors such as temperature sensors and speed sensors,
many controllers such as engine controllers and break controllers,
many power electricity such as an engine starter and a power steering,
many lights such as head lights and break lamps, and many
additional systems such as a global positioning system, a CD
player, sound speakers and a radio.  Consequently a large number of
electric wires run in the body of a car in a complicated manner.

In a bundle of electric wires used
in an actual car, a set of wires of
various sizes are collected together into a cylinder-like bundle,
and many bundles are again collected together into a larger bundle.
In order to layout those bundles of wires, we have to make holes
on walls of the body through which the wires pass.  Those holes
should be large enough for the bundle of wires to pass, but
we do not want to make them unnecessarily large because larger
holes will weaken the body.

Hence, we want to estimate the size of a bundle of wires as precisely as
possible in order to determine the sizes of the holes.  From the
precision point of view the best way is to actually make a bundle
using real wires.  However we do not want to do that, because we want
to know the appropriate sizes of the holes in the design stage,
where everything is just on sheets of paper or in computers.
Thus, given a set of the sizes of wires, we want to estimate the
size of the bundle that would be generated when we put them
together tightly.  This is the problem we consider in this paper.

Considering the cross section of a wire bundle, we may reduce the
problem into a two-dimensional disk packing problem, that is,
given a set of disks (corresponding to the cross sections of wires),
we want to find the smallest enclosing circle that encloses all the
disks without overlap.

Disk packing is an old and hard problem, and has been studied by
many mathematicians.  Examples of old work can be found in
Goldberg \cite{goldberg} and Kravitz \cite{kravitz}.
Since these days, various types of packing problems have been studied.
They include packing disks in a circle \cite{lubachevsky},
packing disks in a square \cite{mollard},
and packing disks on a sphere \cite{goldberg}.
They search for the smallest size of the enclosing figure in a
strict sense, and gave solutions only to some restricted numbers of
disks. Moreover, they concentrate their attention onto the case where
all the disks are of the same size.  Actually there is almost no
result for disks with different sizes.

Fortunately, however, what we want in order to estimate the size of
a wire bundle is not the strictly smallest enclosing circle, but
an approximation that is nearly smallest. Such enclosing circles
were studied by Drezner and Erkut \cite{drezner}; they reduced the
problem to a nonlinear optimization problem, but they reported that
their method was time consuming and could compute the circles enclosing
up to 23 disks.  What we want, on the other hand, is an enclosing
circle that encloses several hundreds of disks with different sizes,
and hence we cannot use the previous methods.

In this paper, we propose a new method for finding a small circle that encloses
a given set of disks with different sizes.  Intuitively speaking,
this method simulates a physical process in which we shake the disks
inside the enclosing circle while we shrink the enclosing circle step by
step until the disks cannot move any more.

\section{Bundle Coefficient Approach} %2

Let us denote by $c_i$ a disk with radius $r_i$.  The location of $c_i$
is not fixed; we can move $c_i$ in the plane freely.  Suppose that we
are given a set $C=\{ c_1, c_2, \cdots , c_n\}$ of $n$ such disks.
Our goal is to find a nearly smallest circle that encloses all the
disks without overlap in reasonably small computation time.

Table \ref{tab1} shows an example a disk set that actually arises
in an existing car.  In this table, the left column shows the category
names of wires, the middle column shows the radii of the perpendicular
sections of the wires, and the right column shows the number of wires
belonging to each category and each size.  Hence, in this example, the
bundle contains 162 wires, among which the largest one is more than
three times larger in radius than the smallest one.
\begin{table}[htbp]
\begin{center}
\caption{Wires belonging to a bundle in an actual car.}
\vspace{2mm}
\label{tab1}
\begin{tabular}{ccc}
\hline
category of a wire & radius (mm) & number\\
\hline
23A & 1.8 & 3 \\
20G & 0.7 & 11 \\
31G & 0.8 & 31 \\
44G & 0.9 & 5 \\
45G & 1.05 & 9 \\
51G & 1.3 & 12 \\
25J & 0.55 & 25 \\
28J & 0.65 & 54 \\
30J & 0.75 & 1 \\
31J & 0.9 & 6 \\
22X & 0.9 & 4 \\
10E & 1.75 & 1 \\
\hline
total & & 162\\
\hline
\end{tabular}
\end{center}
\end{table}

We first describe what is currently being done in industry.  They have a secret
number, say $B$, called a ``bundle coefficient''.
Let $S$ be the sum of the areas of the disks:
$$ S= \sum_{i=1}^n \pi {r_i}^2.$$
Then, they estimate the diameter of the bundle by $B\sqrt{S}$.

This estimation is based on the assumption that in the section of
a wire bundle, the ratio of the area occupied by the wires to the
empty area is constant.

However, this is not true in general.  A typical example is shown in
Fig.~\ref{fig2}.  Fig.~\ref{fig2}(a) shows the case where all the
disks are equal in size, and they are packed tightly in the way
just like a nest of bees.  In Fig.~\ref{fig2}(b), on the other hand,
additional smaller disks are inserted in the empty space.
Therefore, the ratio of the occupied area is larger in Fig.~\ref{fig2}(b)
than in Fig.~\ref{fig2}(a).  This example implies that the
bundle-coefficient method does not work well, because the distribution
of wire sizes changes from bundle to bundle.
\begin{figure}[htb]
\begin{center}
\includegraphics[scale=0.2]{fig1a.eps} \hspace{1cm}
\includegraphics[scale=0.2]{fig1b.eps}\\
 (a) \hspace{5.4cm} (b)
\caption{Two packings in which the ratio of the empty space is different.}
\label{fig2}
\end{center}
\end{figure}

Actually there are more than one bundle coefficient in industry, and
experienced persons select according to their inspiration the one
that seems the most suitable for each set of wires.
This kind of estimation cannot guarantee the quality of the result,
and hence a more logical method is required.

\section{Shrink-and-Shake Algorithm} %3

In this section we present the basic structure of the proposed algorithm.
First, we show an example of the behavior of our algorithm, next
sketch the basic structure, and then describe how to simulate shaking
disks in a circle.

\section{Concluding Remarks} %6

In this paper, we reduced the problem of estimating the size of a wire
bundle to the two-dimensional disk packing problem, and proposed a
shrink-and-shake method for solving this problem (Algorithm 1).
The proposed method is heuristic in its nature, but the experiments
show that the output is stable in the sense that the variance of
the estimated size of the enclosing circle is very  small.
Moreover, the size of the enclosing circle obtained by our algorithm
is close to the actual size of the wire bundle; it is actually close
enough for our original goal of estimating the size of the hole
we should make.

From the time complexity point of view, we presented two methods, a
naive method (Algorithm 2) and an improved method (Algorithm 3), for the
main part of the shrink-and-shake procedure. Experiments show that
the improved method gives better performance for large numbers of disks.
Also we found that the naive method is useful to solve moderate sizes
of problems arising in actual industry.

Our next question is how large the number of disks for the improved method
to show a better performance than the naive method in the case where
the sizes of disks are different.  This is one of our future problems.

There are many related problems for future.  In order to make a better
estimation of the size of a wire bundle, we need to consider the friction
of insulator and the three-dimensional structure of wires.

In this paper we presented the shrink-and-shake strategy, but other
strategies might be also possible.  For example, when we push the
protruding disk toward inside the enclosing circle, the force propagates
from disk to disk.  This physical phenomenon can also be formulated
in a mathematical manner in order to get another strategy.

As for the disk packing problem, we can consider many variants.
For example, other problems are obtained when we replace the
enclosing circle with other shapes, such as an enclosing square,
an enclosing rectangle, an enclosing triangle and an enclosing
ellipse.  It might be also a challenge to consider a non-convex
enclosing shape.

\begin{thebibliography}{9}

\bibitem{drezner}
Z.~Drezner and E.~Erkut: Solving the continuous $p$-dispersion problem
using non-linear programming.
{\it Journal of the Operations Research Society}, vol.~46 (1995), pp.~516--520.

\bibitem{goldberg}
M.~Goldberg: Packing of 18 equal circles on a sphere.
{\it Elements of Mathematics}, vol.~20 (1965), pp.~59--61.

\bibitem{kravitz}
S.~Kravitz: Packing cylinders into cylindrical containers. {\it Mathematical
Magazine}, vol.~40 (1967), pp.~65--71.

\bibitem{lubachevsky}
B.~D.~Lubachevsky and R.~L.~Graham: Curved hexagonal packings of equal
disks in a circle. {\it Discrete and Computational Geometry},
vol.~18 (1997), pp.~179--194.

\bibitem{mollard}
M.~Mollard and C. Payan: Some progress in the packing of equal circles
in a square. {\it Discrete Mathematics}, vol.~84 (1990), pp.~303--307.

\end{thebibliography}

\end{document}
