MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

2 added 284 characters in body

The definitive (and recent!) work on this topic, from the asymptotic complexity point of view (which I emphasized in my comment) is due to Esther Ezra, a student of Micha Sharir. See especially the paper from her Ph.D. thesis, "On the Union of Cylinders in Three Dimensions," Discrete & Computational Geometry, Volume 45, Issue 1, January 2011, Pages 45-64 (ACM link; PDF download link). From the Abstract:

We show that the combinatorial complexity of the union of $n$ infinite cylinders in $\mathbb{R}^3$, having arbitrary radii, is $O(n^{2+\epsilon})$, for any $\epsilon>0$; the bound is almost tight in the worst case, thus settling a conjecture of Agarwal and Sharir ...

Deeper into the paper:

We note that it is crucial to assume that the cylinders are inﬁnite. Otherwise, the combinatorial complexity of their union is $\Omega(n^3)$ in the worst case. Indeed, suppose we have a set of $n$ cylinders, each of which with a sufﬁciently large radius and height that is arbitrarily close to $0$. We can now arrange these cylinders in a (three-dimensional) grid-like structure, resulting in $\Omega(n^3)$ holes in the union; see Figure 1(a).

The general theorem I had in mind in my (hasty) comment is that, $n$ algebraic surface patches in $\mathbb{R}^d$ define an arrangement of combinatorial complexity of $O(n^d)$, where the constant of proportionality depends on $d$ and the maximum degree of the algebraic surfaces and of the polynomials defining their boundaries. This can be found on p.533 of The Handbook of Discrete and Computational Geometry, Theorem 24.1.4, in a chapter by Dan Halperin.

I believe a closed, end-capped, finite cylinder can be partitioned into four surface patches satisfying the preconditions of this theorem. So we should have $\Omega(n^3)$ from the coins example above, and $O(n^3)$ from this general theorem, and so $\Theta(n^3)$ asymptotically.

1

The definitive (and recent!) work on this topic, from the asymptotic complexity point of view (which I emphasized in my comment) is due to Esther Ezra, a student of Micha Sharir. See especially the paper from her Ph.D. thesis, "On the Union of Cylinders in Three Dimensions," Discrete & Computational Geometry, Volume 45, Issue 1, January 2011, Pages 45-64 (ACM link; PDF download link). From the Abstract:

We show that the combinatorial complexity of the union of $n$ infinite cylinders in $\mathbb{R}^3$, having arbitrary radii, is $O(n^{2+\epsilon})$, for any $\epsilon>0$; the bound is almost tight in the worst case, thus settling a conjecture of Agarwal and Sharir ...

Deeper into the paper:

We note that it is crucial to assume that the cylinders are inﬁnite. Otherwise, the combinatorial complexity of their union is $\Omega(n^3)$ in the worst case. Indeed, suppose we have a set of $n$ cylinders, each of which with a sufﬁciently large radius and height that is arbitrarily close to $0$. We can now arrange these cylinders in a (three-dimensional) grid-like structure, resulting in $\Omega(n^3)$ holes in the union; see Figure 1(a).

The general theorem I had in mind in my (hasty) comment is that, $n$ algebraic surface patches in $\mathbb{R}^d$ define an arrangement of combinatorial complexity of $O(n^d)$, where the constant of proportionality depends on $d$ and the maximum degree of the algebraic surfaces and of the polynomials defining their boundaries. This can be found on p.533 of The Handbook of Discrete and Computational Geometry, Theorem 24.1.4, in a chapter by Dan Halperin.