# The union of unit balls has quadratic complexity, even if they all contain the origin

## 1 Introduction

The union of a set of $`n`$ balls in $`^3`$ has quadratic complexity $`\mathrm{\Theta }(n^2)`$, even if they all have the same radius. All the already known constructions have balls scattered around, however, and Sharir posed the problem whether a quadratic complexity could be achieved if all the balls (of same radius) contained the origin.

In this note, we show a construction of $`n`$ unit balls, all containing the origin, whose union has complexity $`\mathrm{\Theta }(n^2)`$. As a trivial observation, we observe that the centers are arbitrarily close to the origin in our construction. In fact, if the centers are forced to be at least pairwise $`\epsilon `$ apart, for some constant $`\epsilon >0`$, then no more than $`O(\frac{1}{\epsilon ^3})`$ can meet in a single point, and hence the union has complexity at most $`O(\frac{1}{\epsilon ^3}n)=O_\epsilon (n)`$. It is an interesting open question what a condition should be so that the union have subquadratic complexity and yet the balls have arbitrarily close centers.

By contrast, the intersection of $`n`$ balls can have quadratic complexity if their radii are not constrained, but the complexity is linear if all the radii are the same . Similarly, the convex hull of $`n`$ balls can have also quadratic complexity , but that complexity is linear if they all have the same radius.

## 2 Construction

Let $`m`$ and $`k`$ be any integers. We define two families of unit balls: the first consists of $`k`$ unit balls whose centers lie on a small vertical segment; the second consists of $`m`$ unit balls whose centers lie on a small circle under the segment. (See Figure 3.) We show below that their union has quadratic $`O(km)`$ complexity.

### The balls $`B_1`$$`B_k`$.

We denote by $`B(p,r)`$ the ball centered at $`p`$ and of radius $`r`$. Let $`n=k+m`$ and $`P_i`$ denote the point of coordinates $`(0,0,(i1)/n^4)`$, and $`B_i=B(P_i,1)`$, for $`i=1,\mathrm{},k`$. It is clear that the boundary of $`_{1ik}B_i`$ consists of two hemispheres belonging to $`B_1`$ and $`B_k`$ linked by a narrow cylinder of height less than $`k/n^41/n^3`$. This cylinder contains all the circles $`B_iB_{i+1}`$ for $`i=1,\mathrm{},k1`$. (See Figure 1.)

### The balls $`B_{k+1}`$$`B_{k+m}`$.

Let $`R`$ be the point of coordinates $`(x,0,z)`$ with

$$x=\frac{2n^24}{n^4},z=\frac{2n^24}{n^3}.$$

(Any values satisfying the constraints $`P_kH<1`$ in (1) and $`\mathrm{}<\frac{2}{n}`$ in (2) below would do.) We define $`\theta `$ as the rotation around the $`z`$-axis of angle $`2\pi /m`$, and for each $`j=1,\mathrm{},m`$, $`R_{k+j}=\theta ^{j1}(R)`$ and $`B_{k+j}=B(R_{k+j},1)`$.

## 3 Analysis

By our choice of $`x`$ and $`z`$, we prove below that the boundaries of $`B_{k+1}`$ and of the union $`_{i=1}^kB_i`$ depicted in Figure 1 meet along a curve $`\gamma `$ which satisfies the two claims below. The situation is depicted on Figure 2.

###### Claim 1

The curve $`\gamma `$ intersects all the balls $`B_i`$ for $`i=0,\mathrm{},k`$, .

###### Claim 2

The portion of $`\gamma `$ which does not belong to $`B_1`$ (equivalently, which belongs to the union $`_{i=2}^kB_i`$) is contained in an angular sector of angle at most $`2\pi /m`$.

From claim 2, we conclude that the portion of $`\gamma `$ which does not belong to $`B_1`$ is contained in the boundary of the union of the $`n=k+m`$ balls, From claim 1, we conclude that the portion of $`\gamma `$ which does not belong to $`B_1`$ has complexity $`\mathrm{\Omega }(k)`$. From claim 2, that it is contained in a small angular sector, hence appears completely on the boundary of the union of the $`n=k+m`$ balls, and it is replicated $`m`$ times, once for each of the balls $`B_j`$, $`j=1,\mathrm{},m`$. It follows that the union of all the balls $`B_i`$ for $`i=1,\mathrm{},k+m`$ has quadratic complexity $`\mathrm{\Omega }(km)`$. Moreover, all the balls contain the origin. The union of the $`n`$ balls is depicted on Figure 3.

The proofs involve only elementary geometry and trigonometry. The situation is depicted in Figure 4 and 5. Figure 4 depicts a section in the $`xz`$-plane of the spheres $`B_i`$ and $`B_{k+1}`$ and the point $`M`$, the highest point of intersection of the bounding spheres. The point $`M`$ is also depicted on Figure 2.

### Proof of Claim 1.

It suffices to prove that $`M`$ is higher than $`P_k`$, since then $`\gamma `$ extends higher than $`P_k`$ as well and passes through $`M`$ by symmetry. The lowest point of $`\gamma `$ belongs to $`B_1`$ and is clearly below the origin. The two facts together prove that $`\gamma `$ must intersect all the balls between $`B_1`$ and $`B_k`$.

Let $`H`$ be the point in the $`xz`$-plane on the median bisector of $`R`$ and $`P_k`$, with same $`z`$-ordinate as $`P_k`$. (See Figure 4.) In order to prove that $`M`$ is higher than $`P_k`$, it suffices to prove that $`H`$ belongs to $`B_k`$, since then $`M`$ is farther along the bisector. The two triangles $`QP_kH`$ and $`KRP_k`$ have equal angles, hence they are similar. It follows that

$$P_kH=P_kR\frac{P_kQ}{RK}=\frac{P_kR^2}{2RK}=\frac{x^2+\left(zz_k\right)^2}{2x},$$
(1)   
where $`z_k=\frac{k1}{n^4}`$. For $`x`$ and $`z`$ as given in the construction, we have

$$P_kH=1/16\frac{40n^415n^2+68+16n^616n^3+28n}{n^4\left(n^22\right)}$$

which is smaller than 1 for $`n2`$.

### Proof of Claim 2.

It is easy to see that the intersection of $`\gamma `$ and a ball $`B_i`$ ($`2ik`$) consists of at most two arcs of circle, any of which is monotone in angular coordinates around the $`z`$-axis, and that any such arc is entirely above the plane $`z=0`$. Hence the intersections of $`\gamma `$ with the $`xy`$-plane belong to $`B_1`$ and $`B_{k+1}`$. It suffices to show that these intersections are at a distance $`\mathrm{}`$ at most $`\frac{2}{n}\mathrm{sin}\frac{\pi }{m}`$ from the $`x`$-axis. (See Figure 5.)

In the $`xy`$-plane section, $`B_1`$ is a unit circle, and $`B_{k+1}`$ is a circle of radius $`r=\sqrt{1z^2}`$ and center $`R^{}`$ of coordinates $`(x,0)`$. (Recall that the center of $`B_{k+1}`$ has coordinates $`(x,0,z)`$.) Hence $`\mathrm{}`$ is the height of a triangle with base $`x`$ and sides 1 and $`r<1`$. It is elementary to compute that

$$\mathrm{}=\sqrt{1\left(\frac{z^2+x^2}{2x}\right)^2}.$$
(2)   
For our choice or $`x`$ and $`z`$, this yields

$$\mathrm{}=\sqrt{\frac{2n^6+3n^44n^24}{n^8}}$$

which is smaller than $`2/n`$ for $`n2`$.

### Acknowledgments.

Thanks to Micha Sharir for pointing out the problem the us. It was also pointed out that Alon Efrat might have a construction which leads to a quadratic lower bound as well. We have derived our construction independently.