Circle Packing and Fiber Stuffing

August 10, 2008 | 2 Minute Read

Now that the Ifos project is nearing completion—at least, the device itself is almost ready for actual live testing in an actual live installation—a practical question has come up.

I’m beginning to wonder just how many stars will one slave be able to handle. Even a rough order of magnitude would be useful. Are we talking 100 or 10,000?

$$\begin{align} count\approx\frac{\pi(\frac{D}{2})^2}{\pi(\frac{d}{2})^2} &=\left(\frac{D^2}{4}\right)\left(\frac{4}{d^2}\right) =\frac{D^2}{d^2}\tag{1} \end{align}$$

A quick-and-dirty estimate for the capacity of a single LED, say, would simply divide the cross-sectional area of the lens by that of the average fiber. The equation above does this for lens diameter $D$ and fiber diameter $d$, but doesn’t account for gaps in a bundle of fibers. Not a problem… I’m not looking for an exact answer. I could take $count$ as an upper bound and assume a rough error factor of, what? 20%?

I discovered that computing that error factor is a lot harder than I thought. I figured the problem must be pretty common, though. How do engineers compute the minimum conduit needed to carry $N$ wires, or the number of conductors that will fit in a cable of a specific size? In fact, the problem is a well-known subject of continuing mathematical research, referred to as circle packing.

Lucky for me, Fiber Optics Systems provides an online calculator to compute exactly the number I was after. The relevant formula, based on an Excel spreadsheet (as indicated by the page source), looks like:

$$count=3\times[\texttt{POWER}((\texttt{ODD}(D/d)-1)/2,2)-(\texttt{ODD}(D/d)-1)/2]+1$$

Interesting. How does ODD() come into play? It turns out to be ceiling with a twist:

$$\begin{align*} count&=3\times\left[\left(\frac{\texttt{ODD}(D/d)-1}{2}\right)^2-\left(\frac{\texttt{ODD}(D/d)-1}{2}\right)\right]+1\\ &=3\left(\left\lceil\frac{\frac{D}{d}-1}{2}\right\rceil^2-\left\lceil\frac{\frac{D}{d}-1}{2}\right\rceil\right)+1\\ &=3u^2-3u+1\qquad\mbox{for }u=\left\lceil\frac{\frac{D}{d}-1}{2}\right\rceil\tag{2} \end{align*}$$

Rearranging terms we obtain:

$$\begin{align} u=\left\lceil\frac{\frac{D}{d}-1}{2}\right\rceil =\left\lceil\frac{D}{2d}-\frac{1}{2}\right\rceil \stackrel{?}{=}\left\lfloor\frac{D}{2d}+\frac{1}{2}\right\rfloor\tag{3} \end{align}$$

Does the last version look familiar? It resembles the old programmer’s hack to round a number: add 0.5 and truncate. Here’s where the twist comes in, however. When rounding, the next higher number is chosen for fractional parts ≥ 0.5; equation 3 returns the next higher number only for fractional parts strictly > 0.5. If not for this small but significant difference, the ceiling operation could be replaced with a simple cast.

The web calculator answered my question easily, by the way. A 5mm LED can handle up to 61 fibers 0.5mm across, provided they’re packed optimally. That’s significantly lower than 100, the guesstimate returned by equation 1. Let’s be safe and call it 50. Assuming all 16 general purpose LEDs are devoted to medium-sized stars, each slave should therefore be able to handle about 800. Not too bad.