<figure><img src="image_1.png" /></figure>

HAL
open science

# On the Complexity of Sets of Free Lines and Line Segments Among Balls in Three Dimensions

Marc Glisse, Sylvain Lazard

► To cite this version:

Marc Glisse, Sylvain Lazard. On the Complexity of Sets of Free Lines and Line Segments Among Balls in Three Dimensions. 26th annual symposium on Computational geometry - SoCG 2010, Jun 2010, Snowbird, Utah, United States. 10.1145/1810959.1810969. inria-00442751v2

HAL Id: inria-00442751

https://inria.hal.science/inria-00442751v2

Submitted on 17 Mar 2010

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# On the Complexity of Sets of Free Lines and Line Segments Among Balls in Three Dimensions

Marc Glisse

INRIA Saclay Île de France
Orsay, France

marc.glisse@inria.fr

Sylvain Lazard

INRIA Nancy Grand Est, LORIA laboratory
Nancy, France

sylvain.lazard@inria.fr

## ABSTRACT

We present two new fundamental lower bounds on the worst-case combinatorial complexity of sets of free lines and sets of maximal free line segments in the presence of balls in three dimensions.

We first prove that the set of maximal non-occluded line segments among $n$ disjoint unit balls has complexity $\Omega(n^4)$, which matches the trivial $O(n^4)$ upper bound. This improves the trivial $\Omega(n^2)$ bound and also the $\Omega(n^3)$ lower bound for the restricted setting of arbitrary-size balls [Devillers and Ramos, 2001]. This result settles, negatively, the natural conjecture that this set of line segments, or, equivalently, the visibility complex, has smaller worst-case complexity for disjoint fat objects than for skinny triangles.

We also prove an $\Omega(n^3)$ lower bound on the complexity of the set of non-occluded lines among $n$ balls of arbitrary radii, improving on the trivial $\Omega(n^2)$ bound. This new bound almost matches the recent $O(n^{3+\epsilon})$ upper bound [Rubin, 2010].

## Categories and Subject Descriptors

F.2.2 [Theory of Computation]: Analysis of Algorithms and Problem Complexity—*Geometrical problems and computations*

## General Terms

Theory

## Keywords

3D visibility, visibility complex, free lines, free segments, balls

## 1. INTRODUCTION

Given a set of objects in $\mathbb{R}^3$, a line is said to be *free* if it does not intersect the interior of any object (we assume here that all objects have a non-empty interior). A maximal

*free line segment* is a (possibly infinite) segment that does not intersect the interior of any object and is not contained in any other segment satisfying the same property. We are interested here in the worst-case combinatorial complexity of sets of free lines, and sets of maximal free line segments.

Free lines and line segments play an important role in several topics in computational and combinatorial geometry. In particular, they play a central role in 3D visibility problems, such as the problem of determining the occlusion between two objects in a three-dimensional scene. In many applications, visibility computations are well-known to account for a significant portion of the total computation cost. Consequently, a large body of research is devoted to speeding up visibility computations through the use of data structures (see [14] for a survey). One such structure, the visibility complex [15, 23], encodes visibility relations by, roughly speaking, partitioning the set of maximal free line segments into connected components of segments tangent to the same set of objects. The vertices of this structure correspond, generically, to the maximal free line segments that are tangent to four objects in the scene, and the total number of faces, from dimension zero to four, is exactly the combinatorial complexity of the space of maximal free line segments. The space of free lines in the presence of balls is also closely related, as noted by Agarwal et al. [1], to motion planning of a line among balls, or, equivalently, of a cylindrical robot (of infinite length) moving among points or balls. This is also related to computing largest empty cylinders among points in three dimensions, ray shooting, and other problems in geometric optimization.

## *Previous work.*

For scenes where the objects are $n$ triangles, the worst-case complexity of the space of free lines (or lines, for short) or maximal free line segments (or segments, for short) can easily be seen to be $\Theta(n^4)$ [8]. When the triangles form a terrain, the same bound of $\Theta(n^4)$ holds for segments [9] and a near-cubic lower bound was proved for lines by Halperin and Sharir [17] and Pellegrini [22]. De Berg et al. [10] showed an $\Omega(n^3)$ lower bound and an almost matching $O(n^2\lambda_4(n))$ upper bound<fnref n="1" /> on the complexity of the set of free lines among $n$ disjoint homothetic polytopes (i.e., convex polyhedra) of constant complexity. The lower bound of $\Omega(n^3)$ also applies to the set of free segments, because any lower bound on the complexity of the set of free lines trivially holds for segments

<footnote n="1">¹Recall that $\lambda_4(n)$ denotes an almost linear function equal to the maximum length of an $(n, 4)$-Davenport-Schinzel sequence [3].</footnote>
<table><caption>Table 1: Known bounds on the worst-case combinatorial complexity of sets of free lines and maximal free line segments (results presented in this paper are shown in bold).</caption><thead><tr><th></th><th colspan="2">Free lines</th><th colspan="2">Free line segments</th></tr></thead><tbody><tr><td>Triangles</td><td colspan="2">Θ(n<sup>4</sup>)</td><td colspan="2">Θ(n<sup>4</sup>)</td></tr><tr><td>Polyhedral terrain</td><td>Ω(n<sup>3</sup>2<sup>c√log n</sup>)</td><td>O(n<sup>4</sup>)</td><td colspan="2">Θ(n<sup>4</sup>)</td></tr><tr><td>k disjoint homoth. polytopes</td><td>Ω(k<sup>3</sup>)</td><td>O(k<sup>2</sup>λ<sub>4</sub>(k))</td><td>Ω(k<sup>3</sup>)</td><td>O(k<sup>4</sup>)</td></tr><tr><td>k polytopes of total size n</td><td>Ω(n<sup>2</sup> + nk<sup>3</sup>)</td><td>O(n<sup>2</sup>k<sup>2</sup>)</td><td colspan="2">Θ(n<sup>2</sup>k<sup>2</sup>)</td></tr><tr><td>Unit balls</td><td>Ω(n<sup>2</sup>)</td><td>O(n<sup>3+ε</sup>)</td><td colspan="2">Θ(n<sup>4</sup>)</td></tr><tr><td>Arbitrary balls</td><td>Ω(n<sup>3</sup>)</td><td>O(n<sup>3+ε</sup>)</td><td colspan="2">Θ(n<sup>4</sup>)</td></tr></tbody></table>

as well.

When the triangles are organized into $k$ polytopes of total complexity $n$, with $k \ll n$, better bounds can be obtained. For the case of disjoint polytopes in general position, Efrat et al. [16] proved a worst-case bound of $O(n^2k^2)$ on the complexity of the set of free segments. When the $k$ polytopes may intersect, Brönnimann et al. [5] proved, independently, the tight bound of $Θ(n^2k^2)$; their lower bound holds for disjoint polytopes, and their upper bound extends to polytopes in degenerate configurations. Any upper bound on the complexity of the set of segments trivially holds for lines as well. Thus, for free lines among $k$ polytopes of total complexity $n$, the upper bound of $O(n^2k^2)$ holds. However, the best known lower bound is $Ω(n^2 + nk^3)$, in which $Ω(n^2)$ follows from the bound of $Ω(n^2k^2)$ on maximal free line segments for $k = 4$, and $Ω(nk^3)$ can be obtained by slightly modifying the lower-bound construction [12](Th.9) proving that the umbra cast on a plane by one segment light source in the presence of $k$ disjoint polytopes of total complexity $n$ can have $Ω(nk^2)$ connected components (one simply has to consider $k$ perturbed copies of the segment light source).

Much less is known for curved objects. For $n$ unit balls, Agarwal et al. [1] proved an upper bound of $O(n^{3+ε})$, for any $ε > 0$, on the complexity of the space of free lines. Rubin [24] recently extended this result to balls of arbitrary radii. Devillers et al. [13] showed a simple bound of $Ω(n^2)$ on the number of vertices of this free space (note that a trivial $Ω(n^2)$ bound on the complexity of the whole space is obtained by considering sparsely distributed balls on two parallel planes). For $n$ balls of arbitrary radii, Devillers and Ramos (personal communication 2001, see also [13]) showed an $Ω(n^3)$ lower bound on the complexity of the set of free line segments and the trivial upper bound of $O(n^4)$ holds.

### Our results.

Our main contribution is a tight worst-case bound of $Θ(n^4)$ on the space of maximal free line segments among unit balls, or, equivalently, on the visibility complex of unit balls. This bound improves the trivial bound of $Ω(n^2)$ for unit balls and also the $Ω(n^3)$ lower bound for balls of arbitrary radii. This result is particularly surprising because it was natural to conjecture that the visibility complex of fat objects of similar size had a lower worst-case complexity than that for thin triangles. Our result settles negatively this conjecture, and shows exactly the opposite, that is, that fatness and similarity, alone, do not reduce the worst-case complexity of that structure.

Our second result is a worst-case lower bound of $Ω(n^3)$

on the complexity of the space of free lines among balls of arbitrary radii. This bound improves the trivial $Ω(n^2)$ bound and almost matches the $O(n^{3+ε})$ upper bound recently proved by Rubin [24].

The complexity results discussed so far are summarized in Table 1.

### Related work.

The complexity of the space of maximal free line segments has also been studied in a random setting. Devillers et al. [13] proved that, in the presence of uniformly distributed unit balls, this structure has complexity $Θ(n)$.

Related literature on free lines and line segments among objects fall in various categories. One deals with characterizing sets of lines tangent to four objects, such as balls or triangles, possibly in degenerate configuration (see [4, 6, 7, 19, 20, 21]). Another related line of research focuses on sets of lines that intersect objects and, in particular, on the complexity of the space of line transversals to a set of objects. For $n$ balls, Agarwal, et al. [2] showed an $Ω(n^3)$ lower bound and a $O(n^{3+ε})$ upper bound. For $k$ polytopes of total complexity $n$, Kaplan et al. [18] recently proved a $O(n^2k^{1+ε})$ upper bound.

### Paper organization.

We prove in Section 2 the $Ω(n^3)$ lower bound on the complexity of the space of free lines among $n$ balls. In Section 3, we prove the bound of $Θ(n^4)$ on the space of maximal free line segments among $n$ unit balls.

We will describe our lower-bound constructions using a Cartesian coordinate system $(x, y, z)$. In this coordinate system, we denote by $M_x$, $M_y$ and $M_z$ the coordinates of a point $M$ (or also the coordinates of the center of a ball $M$).

## 2. FREE LINES TANGENT TO BALLS

We prove here the following result.

**THEOREM 1.** *The combinatorial complexity of the space of free lines among $n$ disjoint balls is $Ω(n^3)$ in the worst case.*

We prove Theorem 1 with a lower-bound construction. For convenience, our construction involves $3n + 3$ balls instead of just $n$, which does not affect the asymptotic complexities.

Refer to Figure 1. We define a set $S$ of disjoint balls that consists of the following three subsets of $n + 1$ balls. We consider first a set of unit balls $B = \{B_0...B_n\}$ whose
<figure><img src="image_3.png" /><figcaption>Figure 1: Illustration of our construction for Theorem 1.</figcaption></figure>

centers are aligned along the x-axis with coordinates $(3(i - n/2), 0, 0)$. We then consider two sets of balls, $A^- = \{A_0^- \dots A_n^-\}$ and $A^+ = \{A_0^+ \dots A_n^+\}$, of sufficiently small radius $\epsilon$ and whose centers are aligned on two lines parallel to the y-axis in the plane $z = 1$. As we will see in Lemma 4, we require $\epsilon < \frac{1}{5400n^2}$. The center of $A_i^-$ has coordinates $(-3n, 3(i - n/2)\epsilon, 1)$, and $A_i^+$ is its reflection with respect to the yz-plane.

We prove Theorem 1 by proving the following bound. A line tangent to a set of balls is said to be *isolated* if it cannot be moved continuously while remaining tangent to these balls.

**PROPOSITION 2.** There are $\Omega(n^3)$ isolated free lines tangent to any four of the balls of $S$.

The idea of the proof is as follows. Consider only two consecutive balls $B_i$ and $B_{i+1}$. We study the lines that are tangent to them close to their north poles (i.e., their points with maximum z-coordinate). These lines are almost in the horizontal plane $z = 1$. Now, in this plane, the balls in $A^-$ and $A^+$ form two sets of gates which decompose the set of free lines in $\Omega(n^2)$ connected components defined by the gates the line goes through. On the boundary of each such component, there are lines tangent to one ball of $A^-$ and one of $A^+$. There are thus $\Omega(n^2)$ free lines tangent to one ball of $A^-$, one of $A^+$, and two consecutive balls of $B$. Since this can be done for any two consecutive balls of $B$, there are $\Omega(n^3)$ free lines tangent to four balls. Moreover, since the centers of these balls are not aligned, these tangents are isolated [4].

We now give a formal proof of Proposition 2. The first step of the proof is to prove the following technical lemma which formalizes the fact that the considered tangent lines to two consecutive balls in $\mathcal{B}$ lie almost in the horizontal plane through their north poles.

Let $\tilde{B}_0$ and $\tilde{B}_1$ be two unit balls centered at $(0, 0, 0)$ and $(3, 0, 0)$ and let $L$ be a line tangent to $\tilde{B}_0$ and $\tilde{B}_1$ respectively at $M_0 = (x_0, y_0, z_0)$ and $M_1 = (x_1, y_1, z_1)$ in their northern hemispheres (that is, such that $z_0$ and $z_1$ are positive). Lemma 3 states, roughly speaking, that, as the y-coordinates of $M_0$ and $M_1$ go to 0, the z-coordinates converge *quadratically* to 1.

**LEMMA 3.** If $|y_0|$ and $|y_1|$ are smaller than some constant $m < 1/25$ and $|y_1 - y_0|$ is smaller than some constant $\alpha$, then $z_0$ and $z_1$ are larger than $1 - 100m^2$ and $|z_1 - z_0|$ is smaller than $110m\alpha$.

**PROOF.** We first argue that the result is intuitively clear by showing that it would be straightforward if, instead of balls, we had discs parallel to the yz-plane. Writing that $M_i$ is on $\tilde{B}_i$ gives $x_0^2 + y_0^2 + z_0^2 = 1$ and $(x_1 - 3)^2 + y_1^2 + z_1^2 = 1$. Considering discs instead of balls (that is $x_0 = 0$ and $x_1 = 3$) gives $|z_i| = \sqrt{1 - y_i^2} \ge \sqrt{1 - m^2} \ge 1 - m^2 > 1 - 100m^2$. Furthermore, the difference of the two equations gives $|z_1 - z_0| = \frac{|y_1 + y_0||y_1 - y_0|}{|z_1 + z_0|} < \frac{2m\alpha}{2(1 - m^2)}$ which is less that $2m\alpha$ because $\frac{1}{2(1 - m^2)} < 1$ since $m < 1/25$.

Since the balls are not discs, we need a few more steps. Consider the vertical plane $\Pi$ that contains $L$ and refer to Figure 2. Plane $\Pi$ cuts the two spheres in two circles of centers $N_0$ and $N_1$ and radii $R_0$ and $R_1$. Let $d_i$ denote the
<figure><img src="image_4.png" /><figcaption>Figure 2: For the proof of Lemma 3: balls $\tilde{B}_0$ and $\tilde{B}_1$ viewed from above.</figcaption></figure>

signed distance from the center of $\tilde{B}_i$ to $\Pi$ (that is to $N_i$) such that $d_i$ has the same sign as $N_{iy}$.

First, we prove that $|N_{0y}|$ and $|N_{1y}|$ are smaller than or equal to $5m$. In projection on the $xy$-plane, since $M_0$ and $M_1$ are on $L$, the absolute value of the slope of the projection of $L$ is $\frac{|y_1-y_0|}{|x_1-x_0|} \le 2m$ since $|y_1-y_0| \le 2m$ and $|x_1-x_0| \ge 1$. Now, $N_i$ is in $\Pi$ so its projection on the $xy$-plane is on the projection of $L$. Since $|N_{ix}-x_i| \le 2$ ($M_i$ and $N_i$ are in the same unit ball), $|N_{iy}-y_i| \le 2 \cdot 2m$ and thus $|N_{iy}| \le |y_i| + 4m \le 5m$.

Second, we prove that $|d_i| \le 10m$ and $|d_1 - d_0| < 10\alpha$. Notice that, since the two angles shown on Figure 2 are equal, they have the same cosine, that is

$$N_{iy}/d_i = (x_1 - x_0)/\sqrt{(x_1 - x_0)^2 + (y_1 - y_0)^2}.$$

Since $x_1 - x_0 \ge 1 > 0$ and $m < 1/25$, the right-hand expression can be rewritten as

$$\frac{1}{\sqrt{1 + \left(\frac{y_1 - y_0}{x_1 - x_0}\right)^2}} \ge \frac{1}{\sqrt{1 + 4m^2}} > \frac{1}{2}.$$

We thus have $d_i = \chi N_{iy}$ with $0 < \chi < 2$. This implies that $|d_i| < 2|N_{iy}| \le 10m$ and $|d_1 - d_0| = \chi|N_{1y} - N_{0y}| < 2|N_{1y} - N_{0y}|$. Once again, the projections of $M_0$, $M_1$, $N_0$ and $N_1$ on the $xy$-plane are aligned, so the slope of the projection of $L$ is $(N_{1y} - N_{0y})/(N_{1x} - N_{0x}) = (y_1 - y_0)/(x_1 - x_0)$. Since $M_i$ and $N_i$ lie in ball $\tilde{B}_i$, $|N_{1x} - N_{0x}| \le 5$ and $|x_1 - x_0| > 1$ and, since $|y_1 - y_0| < \alpha$, we have $|N_{1y} - N_{0y}| < 5\alpha$. Hence $|d_1 - d_0| < 10\alpha$.

Third, we prove that $R_i \ge \sqrt{1 - (10m)^2}$ and $|R_1 - R_0| \le 110m\alpha$. The radii of the intersection circles satisfy $d_i^2 + R_i^2 = 1$. This implies that $R_i \ge \sqrt{1 - (10m)^2}$. Also, $(R_1 - R_0)(R_1 + R_0) = -(d_1 - d_0)(d_1 + d_0)$, so

$$|R_1 - R_0| \le 10\alpha \frac{20m}{2\sqrt{1 - (10m)^2}} < 110m\alpha$$

because $1/\sqrt{1 - (10m)^2} < 1.1$ since $m < 1/25$.

We now work in the plane $\Pi$, using a Cartesian coordinate system $(w, z)$ (see Figure 3). Let $\theta$ be the (unsigned) angle between $L$ and the $w$-axis. We have $z_i = R_i \cos \theta$. Therefore, $z_1 - z_0 = (R_1 - R_0) \cos \theta$ and $|z_1 - z_0| \le |R_1 - R_0| < 110m\alpha$, which is the second inequality of the lemma.

Consider now the line in $\Pi$ parallel to $L$ through $N_1$ if $R_1 \le R_0$ and through $N_0$ otherwise, as shown on Figure 3. Remember that the distance between $N_0$ and $N_1$ is at least 1

<figure><img src="image_5.png" /><figcaption>Figure 3: For the proof of Lemma 3: intersection of balls $\tilde{B}_0$ with plane $\Pi$.</figcaption></figure>

and note that we can assume without loss of generality that $\alpha \le 2m$ since $|y_1 - y_0| < 2m$ and when $\alpha \ge 2m$, Lemma 3 is a trivial consequence of the case $\alpha = 2m$. We have that $\sin \theta = |R_1 - R_0|/||N_1 - N_0|| < 110m\alpha \le 220m^2 < 10m$. Hence $\cos \theta > \sqrt{1 - (10m)^2}$. We have already proved that $R_i \ge \sqrt{1 - (10m)^2}$. Therefore $z_i = R_i \cos \theta > 1 - 100m^2$ which concludes the proof. $\square$

We now prove that, roughly speaking, a line tangent to two consecutive balls of $B$ near their north poles intersects each of the convex hulls of $A^-$ and of $A^+$ and thus that the balls of $A^\pm$ play the role of gates as discussed earlier.

Let $L$ be a line tangent to $B_i$ and $B_{i+1}$ ($0 \le i \le n-1$) at some points with positive $z$-coordinate and let $L^+$ and $L^-$ be the points of intersection of $L$ with the planes $x = 3n$ and $x = -3n$, respectively (see Figure 4).

**LEMMA 4.** If $|L_y^+|$ and $|L_y^-|$ are smaller than $3n\epsilon/2$ with $\epsilon < \frac{1}{5400n^2}$, then $|L_z^- - 1|$ and $|L_z^- - 1|$ are smaller than $\epsilon/2$.

**PROOF.** Let $P$ and $Q$ denote the tangency points of $L$ on $B_i$ and $B_{i+1}$ (refer to Figure 4). $L^-$, $P$, $Q$ and $L^+$ are aligned in this order on $L$, and $|L_y^+|$ and $|L_y^-|$ are both smaller than $3n\epsilon/2$, so $|P_y|$ and $|Q_y|$ are smaller than $3n\epsilon/2$. Furthermore, the slope of the projection of $L$ in the $xy$-plane is $\frac{L_y^+ - L_y^-}{L_x^+ - L_x^-} = \frac{Q_y - P_y}{Q_x - P_x}$ and, by hypothesis, $|L_y^+ - L_y^-| \le 3n\epsilon$, $L_x^+ - L_x^- = 6n$ and $|Q_x - P_x| \le 5$, so $|Q_y - P_y| \le 5\epsilon/2$. We can now apply Lemma 3 because $|P_y|$ and $|Q_y|$ are both smaller than $m = 3n\epsilon/2$ which is smaller than $1/25$ since $\epsilon < 1/5400n^2$ and $|Q_y - P_y| \le 5\epsilon/2$. We thus get $|Q_z - P_z| < 110 \frac{3n\epsilon}{2} - \frac{5\epsilon}{2} = 110 \frac{15}{4} n\epsilon^2$ and $Q_z > 1 - 100(\frac{3n\epsilon}{2})^2$. Moreover, since $Q_z \le 1$, we have $|Q_z - 1| < 100(\frac{3n\epsilon}{2})^2$.

$L^-$, $P$, $Q$ and $L^+$ are still aligned on $L$ and we now consider the slope of the projection of $L$ on the $xz$-plane: $\frac{L_z^+ - Q_z}{L_x^+ - Q_x} = \frac{Q_z - P_z}{Q_x - P_x}$. By construction, $|L_x^+ - Q_x| < 6n$ and $Q_x - P_x \ge 1$ so

$$|L_z^+ - 1| - |Q_z - 1| \le |L_z^+ - Q_z| < 6n|Q_z - P_z| < 6 \cdot 110 \frac{15}{4} n^2 \epsilon^2.$$

Moreover, since $|Q_z - 1| < 100 \frac{9}{4} n^2 \epsilon^2$ and $100 \frac{9}{4} + 6 \cdot 110 \frac{15}{4} = 2700$, we have $|L_z^+ - 1| < 2700 n^2 \epsilon^2 < \epsilon/2$ since $\epsilon < \frac{1}{5400n^2}$. The same holds for $|L_z^- - 1|$. $\square$

We can now prove that there are $\Omega(n^3)$ isolated free lines tangent to any four of the balls of $S$.
<figure><img src="image_6.png" /><figcaption>Figure 4: A line $L$ for Lemma 4.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Figure 5: For the proof of Proposition 2: lines $L$ intersect planes $x = \pm 3n$ in the shaded region.</figcaption></figure>

PROOF OF PROPOSITION 2. We prove the proposition by showing that any pair of consecutive balls $B_i, B_{i+1}$ ($0 \le i < n$) and any two balls $A_j^-$ and $A_k^+$ ($j, k \in \{0, \dots, n\}$) admit at least one common tangent free line.

Notice first that any line tangent to $B_i$ and $B_{i+1}$ cannot intersect the interior of any ball $B_j$ and thus can only be occluded by a ball in $\mathcal{A}^\pm$.

In the $xy$-plane, consider the two segments $S^+$ and $S^-$ defined by $x = \pm 3n$ and $-3n\varepsilon/2 < y < 3n\varepsilon/2$ (see Figure 4); as in Lemma 4, we assume $\varepsilon < \frac{1}{5400n^2}$. Any pair of points, one on each of these two segments, defines uniquely a line $L$ that lies in the vertical plane containing these two points and such that $L$ is tangent to $B_i$ and $B_{i+1}$ at points in their northern hemispheres (at points with positive $z$ coordinates). We parameterize these lines by the $y$-coordinates, $u$ and $v$, of the two points on $S^-$ and $S^+$, respectively, defining the line. In the following, $u$ and $v$ are thus restricted to the interval $[-3n\varepsilon/2, 3n\varepsilon/2]$.

Using this parameterization, we consider the set of lines $L(u, v)$ (or, for simplicity, $L$) represented as a square in the $(u, v)$-parameter space. As in the proof of Lemma 4, let $L^\pm$ denote the point of intersection of $L$ and plane $x = \pm 3n$ (note that $u = L_y^-$ and $v = L_y^+$) and recall that the $y$-coordinate of the center of ball $A_j^-$ is denoted $A_{jy}$.

We first show that there exist nonempty intervals $I_j \subset J_j$ of $u$ such that (see Figure 6) the intervals $J_j$ are pairwise disjoint and for all $v$: (i) for all $u \in I_j$, $L(u, v)$ intersects ball $A_j^-$, (ii) for all $u \notin J_j$, $L(u, v)$ does not intersect ball $A_j^-$.

Refer to Figure 5. By Lemma 4, $|L_z^- - 1| < \varepsilon/2$. It follows that $|L_y^- - A_{jy}^-| \le \frac{\sqrt{3}}{2}\varepsilon$ implies that $L$ intersects $A_j^-$ since the square distance between $L^-$ and the center of $A_j^-$ is less than or equal to $(\frac{1}{2}\varepsilon)^2 + (\frac{\sqrt{3}}{2}\varepsilon)^2 = \varepsilon^2$. Hence, any line $L(u, v)$ such that $u = L_y^-$ is in $I_j = [A_{jy}^- - \frac{\sqrt{3}}{2}\varepsilon, A_{jy}^- + \frac{\sqrt{3}}{2}\varepsilon]$ intersects ball $A_j^-$.

We now show that any line $L(u, v)$ that intersects $A_j^-$ satisfies $u \in J_j = [A_{jy}^- - \frac{5}{4}\varepsilon, A_{jy}^- + \frac{5}{4}\varepsilon]$. The slope of the projection of line $L$ onto the $xy$-plane is (in absolute value) $\frac{|L_y^+ - L_y^-|}{|L_x^+ - L_x^-|} \le \frac{3n\varepsilon}{6n} = \frac{\varepsilon}{2}$ (see Figure 4) which is less than $\frac{1}{8}$ since $\varepsilon < \frac{1}{5400n^2}$. Thus, the $y$-coordinate of points on $L$ varies by at most $\frac{\varepsilon}{4}$ in the slab $-3n - \varepsilon \le x \le -3n + \varepsilon$. If $L$ intersects $A_j^-$, one point of $L$ in this slab has its $y$-coordinate in $[A_{jy}^- - \varepsilon, A_{jy}^- + \varepsilon]$, hence $u = L_y^- \in J_j$.

We now partition the set of lines $L$ in parameter space $(u, v)$ as follows (see Figure 6): the dark grey region is the set of $(u, v)$ such that $u$ or $v$ is in some $I_j$; the white region is the set of $(u, v)$ such that neither $u$ nor $v$ belongs to $\cup_j J_j$; the light grey region is the complement of the dark grey and white regions in $[\frac{-3n\varepsilon}{2}, \frac{3n\varepsilon}{2}]^2$.

Finally, consider a line $L(u, v)$ for $(u, v)$ in a connected component of the white region bounded by the $u$-strips $J_j$ and $J_{j+1}$ and by the $v$-strips $J_k$ and $J_{k+1}$ (the hatched region in Figure 6). By the above properties of intervals $I_j$ and $J_j$, if we decrease $u$ (resp. increase $u$), the line $L(u, v)$ while remaining free becomes, at some point in the grey region, tangent to $A_j^-$ (resp. $A_{j+1}^-$). Similarly, while $L(u, v)$ remains free and tangent to $A_j^-$ or $A_{j+1}^-$, if we decrease (resp.
<figure><img src="image_8.png" /><figcaption>Figure 6: For the proof of Proposition 2: A line parameterized by a point $(u,v)$ in the dark grey region intersects a ball in $A^\pm$. If $(u,v)$ lies in the white region, the line intersects no ball in $A^\pm$.</figcaption></figure>

increase) $v$ ($u$ may vary slightly in order to maintain the tangency), $L(u, v)$ becomes, at some point, tangent to $A_k^+$ (resp. $A_{k+1}^+$). In other words, in parameter space $(u, v)$, the white cell is contained in a connected component of the set of free lines $L(u, v)$ which is bounded by lines $L(u, v)$ that are tangent to $A_j^-$, $A_{j+1}^-$, $A_k^+$, or $A_{k+1}^+$; moreover, the vertices of the boundary of the cell correspond to lines $L(u, v)$ that are tangent to $A_j^-$ or $A_{j+1}^-$ and to $A_k^+$ or $A_{k+1}^+$.

Hence, any two consecutive balls $B_i$ and $B_{i+1}$ ($0 \le i < n$) and any two balls $A_j^-$ and $A_k^+$ ($j, k \in \{0, \dots, n\}$) admit at least one common tangent free line. This concludes the proof because any four balls with nonaligned centers admit finitely many common tangents [4]. $\square$

**REMARK.** Although our construction admits $\Theta(n^3)$ isolated free lines tangent to four balls, many four-tuples of balls are aligned and thus have infinitely many common tangents. Perturbing all the balls by a sufficiently small amount would easily ensure that all the four-tuples of balls admit finitely many common tangents while all the $\Theta(n^3)$ isolated free lines remain free and tangent to their respective balls.

### 3. FREE LINE SEGMENTS TANGENT TO UNIT BALLS

We prove here the following theorem.

**THEOREM 5.** The combinatorial complexity of the space of maximal free line segments among $n$ disjoint unit balls is $\Theta(n^4)$ in the worst case.

First notice that the $O(n^4)$ upper bound is trivial. We prove the lower bound by giving a construction. Refer to Figure 7. We define a set $S$ of disjoint balls that consists of the four subsets $A^\pm, B^\pm$ of $n$ or $n+1$ balls each. We consider first a set of unit balls $A^- = \{A_1^- \dots A_n^-\}$ whose centers are almost aligned on the $x$-axis, except that each

ball is slightly higher than the one in front of it (looking from $x = +\infty$). The center of $A_i^-$ has coordinates $(-M - 3i, 0, i\epsilon)$ for some large $M$ and some small positive $\epsilon$. The set $B^- = \{B_0^- \dots B_n^-\}$ consists of unit balls whose centers lie on a helix of axis the $x$-axis; in particular, the centers project onto the $yz$-plane on a circle centered at the origin and of radius slightly smaller than 2. Note that the purpose of this helix is to ensure that the balls are disjoint; if we allowed intersecting balls, we could simply place all these centers on a circle in the plane $x = -M$. The center of $B_i^-$ has coordinates $(-M + 3i, (2-\eta)\sin(\alpha_i), (2-\eta)\cos(\alpha_i))$ where $\alpha_i = \alpha(-\frac{1}{2} + \frac{i}{n})$, $\alpha$ is a positive constant and $\eta$ is a small positive constant. Finally, the sets $A^+$ and $B^+$ are the mirror images of $A^-$ and $B^-$, respectively, with respect to the $yz$-plane. An appropriate set of constants is: $\alpha = \pi/4$, $\eta = \frac{1}{160n^2}$, $\epsilon = \frac{1}{160n^3}$ and $M = cn^3$ for a sufficiently large fixed constant $c$.

We prove Theorem 5 by proving the following bound on the balls of $S$, where a line segment tangent to a set of balls is said to be *isolated* if it cannot be moved continuously while remaining tangent to these balls.

**PROPOSITION 6.** There are $\Theta(n^4)$ isolated free line segments tangent to any four of the balls of $S$.

The idea of the lower-bound construction is as follows. Consider the affine transformation changing $x$ into $x/M$ which flattens the spheres into ellipsoids. When $M$ tends to infinity, the scene changes (as it depends on $M$) and the transformed scene tends to two flat versions of Figure 7(b) on the planes $x = \pm 1$, facing each other. Joining the $\Theta(n^2)$ intersections on each side defines $\Theta(n^4)$ free line segments tangent to 4 of the discs. We prove that, for $M$ sufficiently large, the free line segments tangent to 4 of the ellipsoids still exist. Moreover, each of the free line segments tangent to four ellipsoids remains free and tangent to four balls by the inverse affine transformation.

In order to ensure that the set of balls looks like Figure 7(b), $\eta$ and $\epsilon$ need to be small enough so that, when viewed in the $-x$ direction, the boundary of $A_i^-$ is visible between $B_j^-$ and $B_{j+1}^-$. Furthermore, $M$ needs to be large enough so that the view of $A^-$ and $B^-$ remains combinatorially the same from any point of $A^+$ and $B^+$.

We now give a formal proof of Proposition 6 by first showing that if four balls, taken respectively in $A^-$, $B^-$, $B^+$, $A^+$, admit a common tangent line, then this line contains a free segment that still touches the four balls.

**LEMMA 7.** If four balls $A_i^-, B_j^-, B_k^+, A_l^+$ admit a (possibly occluded) common tangent line $L$, then $L$ contains a free segment tangent to the four balls.

**PROOF.** We parameterize line $L$ by its two points of intersection $P^\pm$ with planes $x = \pm M$ (this is possible because $L$ does not lie in a vertical plane). Let $\tilde{A}_i^\pm$ and $\tilde{B}_j^\pm$ be the two discs obtained by projecting balls $A_i^\pm$ and $B_j^\pm$ onto plane $x = \pm M$.

We first show that any two points on line $L$ and in the slab $-M - 3n - 1 \le x \le -M + 3n + 1$ (which contains all balls $A_1^-, \dots, A_n^-$ and $B_0^-, \dots, B_n^-$) project onto plane $x = -M$ in two points that are at distance less than $\frac{1}{320n^2}$. Consider any plane parallel to the $x$-axis and a Cartesian coordinate system $(x, w)$ in that plane. The slope of the projection of $L$ in that plane is less (in absolute value) than $2/M$; indeed,
<figure><img src="image_9.png" /><figcaption>Figure 7: Illustration of our construction for Theorem 5.</figcaption></figure>

the line $L$ goes through a point on $A_i^-$ and a point on $A_l^+$ and, between these two points, the minimum variation in $x$ is $2M + 2 > 2M$, and the maximum variation in $w$ is $2(1+n\epsilon) < 4$ because it is at most the sum of the distances between the $x$-axis and each of these points; each of these distances is at most 1 plus the distance from the ball center to the $x$-axis, which is at most $n\epsilon$; furthermore, $2(1+n\epsilon) < 4$ since $|\epsilon| < \frac{1}{n}$ by assumption. Thus, the $w$-coordinate of points on $L$ and in the slab $-M-3n-1 \le x \le -M+3n+1$ varies by at most $\frac{2}{M}(6n+2) \le \frac{13n}{M}$ (for $n \ge 4$) which is less than $\frac{1}{320n^2}$ since $M = cn^3 > 13 \cdot 320n^3$ for some sufficiently large constant $c$.

We now prove that line $L$ does not intersect the interior of balls $B_0^-, \dots, B_n^-$ and $A_1^-, \dots, A_{i-1}^-$. Suppose first, for a contradiction, that $L$ intersects the interior of a ball $B_u^-$ at a point $Q_u$, for some $u \ne j$. This point projects onto plane $x = -M$ in a point $\tilde{Q}_u$ strictly inside disc $\tilde{B}_u^-$. By the above argument, this point $\tilde{Q}_u$ is at distance at most $\frac{1}{320n^2}$ from discs $\tilde{A}_i^-$ and $\tilde{B}_j^-$ (since $\tilde{Q}_u$ is at distance at most $\frac{1}{320n^2}$ from the projections of the two points of tangency between $L$ and balls $A_i^-$ and $B_j^-$). We obtain a contradiction by showing that the three discs $\tilde{A}_i^-, \tilde{B}_j^-$ and $\tilde{B}_u^-$, each enlarged by $\frac{1}{320n^2}$, do not have a common intersection. Note that it is sufficient to consider $u = j+1$ because the centers of discs $\tilde{B}_u^-$ are ordered on a half-circle of radius larger than 1 (see Figure 8(a)) and the intersection of the enlarged versions of $\tilde{B}_j^-$ and $\tilde{B}_u^-$ is thus contained in the intersection of the enlarged versions of $\tilde{B}_j^-$ and $\tilde{B}_{j+1}^-$.

Refer to Figure 8(a) and denote by $\tilde{A}_i^-, \tilde{B}_j^-$ and $\tilde{B}_{j+1}^-$ the discs $\tilde{A}_i^-, \tilde{B}_j^-$ and $\tilde{B}_{j+1}^-$ enlarged by $\frac{1}{320n^2}$. We prove

that they have empty common intersection by showing that the rightmost point (i.e, with maximum $y$-coordinate) of intersection, $Q$, of the boundary of discs $\tilde{A}_i^-$ and $\tilde{B}_j^-$ lies outside $\tilde{B}_{j+1}^-$. This is done by showing that the angle $\gamma = \angle(C_{\tilde{B}_j^-}C_{\tilde{A}_i^-}Q)$ is less than half the angle $\delta$ where $\delta = \angle(C_{\tilde{B}_j^-}C_{\tilde{A}_i^-}C_{\tilde{B}_{j+1}^-}) = \frac{\alpha}{n}$ and $C_{\tilde{A}_i^-}$ and $C_{\tilde{B}_j^-}$ denote the centers of the discs $\tilde{A}_i^-$ and $\tilde{B}_j^-$. Let $d$ denote the distance between $C_{\tilde{A}_i^-}$ and $C_{\tilde{B}_j^-}$. The triangle inequality on triangle $O^-C_{\tilde{A}_i^-}C_{\tilde{B}_j^-}$ (where $O^-$ denotes the projection of the origin $O$ on the plane $x = -M$) gives $2 - \eta \le d + i\epsilon$ or also $(\frac{d}{2})^2 \ge (1 - \frac{\eta+i\epsilon}{2})^2$ (since $1 - \frac{\eta+i\epsilon}{2} = 1 - \frac{1}{320n^2} - \frac{i}{320n^3} \ge 1 - \frac{1}{160n^2} > 0$).

On the other hand, $\sin \gamma = \frac{\sqrt{(1+\frac{1}{320n^2})^2-(\frac{d}{2})^2}}{1+\frac{1}{320n^2}}$ and, since $\arcsin z < 2z$ for $z > 0$, we have

$$ 
\begin{align*}
\gamma &< 2 \frac{\sqrt{(1 + \frac{1}{320n^2})^2 - (1 - \frac{\eta + i\epsilon}{2})^2}}{1 + \frac{1}{320n^2}} \\
&< 2 \sqrt{\left(1 + \frac{1}{320n^2}\right)^2 - \left(1 - \frac{\eta + i\epsilon}{2}\right)^2} \\
&< 2 \sqrt{\frac{1}{160n^2} + \frac{1}{320^2n^4} + \eta + n\epsilon} < 2 \sqrt{\frac{1}{80n^2} + \eta + n\epsilon}.
\end{align*}
$$

We have by assumption that $\eta = \frac{1}{160n^2}$, $\epsilon = \frac{1}{160n^3}$ and $\alpha^2 = \frac{\pi^2}{4^2} \approx 0.62 > \frac{4}{10}$, thus $\gamma < 2\sqrt{\frac{1}{40n^2}} < 2\sqrt{\frac{\alpha^2}{16n^2}} = \frac{\alpha}{2n}$ which concludes the proof that $L$ does not intersect the interior of balls $B_0^-, \dots, B_n^-$. We now show that $L$ does not intersect the interior of balls
<figure><img src="image_10.png" /><figcaption>Figure 8: For the proof of Lemma 7: in the plane $x = -M$, (a) discs $\tilde{A}_i^{-}$, $\tilde{B}_j^{-}$, $\tilde{B}_{j+1}^{-}$ and (b) discs $\tilde{A}_i^{-}$ and $\tilde{A}_u^{-}$.</figcaption></figure>

$A_1^-, \dots, A_{i-1}^-$. Recall that the slope of the projection of $L$ onto any plane parallel to the $x$-axis is at most $\frac{2}{M}$. Suppose for a contradiction that $L$ intersects $A_u^-$, $u < i$, at a point $Q_u$ and let $Q_i$ be the intersection of $L$ with plane $x = -M - 3i$ containing the center of ball $A_i^-$. The $x$-coordinates of $Q_u$ and $Q_i$ differ by at most $(-M - 3u + 1) - (-M - 3i - 1) = 3(i-u) + 2 \le 5(i-u)$ (since $1 \le i-u$). The distance between the projections, $\tilde{Q}_u$ and $\tilde{Q}_i$, of $Q_u$ and $Q_i$ onto plane $x = -M$ is thus at most $\frac{2}{M} 5(i-u)$.

We now show that, for $n$ large enough, these two points $\tilde{Q}_u$ and $\tilde{Q}_i$ lie at distance at least $c_0(i-u)\epsilon$ for some constant $c_0$ independent of $M$. This will give that $c_0(i-u)\epsilon \le \frac{10(i-u)}{M}$, hence $\frac{c_0}{160n^3} \le \frac{10}{cn^3}$ which yields a contradiction for $c$ large enough.

Refer to Figure 8(b). First note that, for $n$ large enough, $\tilde{Q}_u$ and $\tilde{Q}_i$ lie inside the wedge of angle $\frac{\pi}{3}$ (or any angle strictly larger than $\frac{\pi}{4}$) centered at $C_{\tilde{A}_u^-}$ (and of axis parallel to the $z$-axis in plane $x = -M$). Indeed, similarly as before, $\tilde{Q}_i$ lies within distance $\frac{1}{320n^2}$ of $\tilde{Q}_u$ which lies in the intersection of the two enlarged discs $\tilde{A}_i^{-}$ and $\tilde{B}_j^{-}$. The center of $\tilde{B}_j^{-}$ lies in a wedge of angle $\frac{\pi}{4}$ centered at $O^-$ (and of axis parallel to the $z$-axis in plane $x = -M$). The claim follows from the fact that, when $n$ goes to infinity, the two apexes converge toward each other and the distance between centers of the two enlarged discs $(\tilde{A}_i^{-}$ and $\tilde{B}_j^{-})$ converges to 2 (from below). Now, since $\tilde{Q}_u$ and $\tilde{Q}_i$ lie inside this wedge and, by definition, $\tilde{Q}_u$ lies inside disc $\tilde{A}_u^-$ and $\tilde{Q}_i$ lies outside disc $\tilde{A}_i^-$, we get that $\tilde{Q}_u$ and $\tilde{Q}_i$ are at distance at least

$c_0(i-u)\epsilon$ for some constant $c_0$.

We have thus proved that line $L$ does not intersect the interior of balls $B_0^-, \dots, B_n^-$ and $A_1^-, \dots, A_{i-1}^-$. We obtain similarly that $L$ does not intersect the interior of balls $B_0^+, \dots, B_n^+$ and $A_1^+, \dots, A_{i-1}^+$. We thus proved that line $L$ may only intersect the interior of balls $A_{i+1}^-, \dots, A_n^-$ and $A_{i+1}^+, \dots, A_n^+$. The slab $-M - 3i - \frac{3}{2} < x < M + 3l + \frac{3}{2}$ contains none of these balls and contains all the other balls, hence the part of the line $L$ in that slab is tangent to $A_i^-, B_j^-, B_k^+, A_l^+$ and is free. $\square$

It remains to show that any four balls $A_i^-, B_j^-, B_k^+, A_l^+$ admit a (possibly occluded) common tangent line.

**PROOF OF PROPOSITION 6.** We have proved in the proof of Lemma 7, that (with the notation introduced in that proof) any triple of enlarged discs $\tilde{A}_i^{-}$, $\tilde{B}_j^{-}$ and $\tilde{B}_{j+1}^{-}$ have an empty intersection.

Denote by $\tilde{A}_i''$, $\tilde{B}_j''$ and $\tilde{B}_{j+1}''$ the discs $\tilde{A}_i^-$, $\tilde{B}_j^-$ and $\tilde{B}_{j+1}^-$ shrunk by $\frac{1}{320n^2}$. We notice that these discs intersect pairwise. $\tilde{B}_j''$ and $\tilde{B}_{j+1}''$ are obviously close enough so that they intersect. For $\tilde{A}_i''$ and $\tilde{B}_j''$ (the third pair is similar), this is a simple consequence of the fact that $\eta \ge 2\frac{1}{320n^2}$.

Hence, any three discs $\tilde{A}_i^-, \tilde{B}_j^-$ and $\tilde{B}_{j+1}^-$ define a non-empty region $R_{i,j}$ (that is, the bounded component of the intersection of the complement of their enlarged versions) shown in grey in Figures 8(a) and 9 and a bounded region $S_{i,j}$ (that is, the bounded component of the intersection of the complement of their shrunk versions) shown in light grey
<figure><img src="image_11.png" /><figcaption>Figure 9: For the proof of Proposition 6.</figcaption></figure>

in Figure 9 that contains $R_{i,j}^{-}$.

We define similarly regions $R_{k,l}^{+}$ and $S_{k,l}^{+}$ in the plane $x = M$. For any $i,j,k,l$, any line through the two regions $R_{i,j}^{-}$ and $R_{k,l}^{+}$ does not intersect $A_{i}^{-}$, $A_{l}^{+}$ nor any ball of $B^{\pm}$. Moving the line continuously, it is impossible to make it escape the set of lines that intersect $S_{i,j}^{-}$ and $S_{k,l}^{+}$ without the line intersecting one of $A_{i}^{-}$, $B_{j}^{-}$, $B_{j+1}^{-}$, $B_{k}^{+}$, $B_{k+1}^{+}$ and $A_{l}^{+}$. Using an argument similar to the one illustrated by Figure 6, we start with a line that intersects $R_{i,j}^{-}$ and $R_{k,l}^{+}$ and move it down until it is tangent to $A_{i}^{-}$ or $A_{l}^{+}$, we then rotate it around the center of that ball in a vertical plane until it is tangent to the other one. We can then move it while it remains tangent to $A_{i}^{-}$ and $A_{l}^{+}$ until it is tangent to $B_{j}^{-}$ and $B_{k}^{+}$. $\square$

# 4. CONCLUSION

We proved a $\Theta(n^4)$ bound on the worst-case combinatorial complexity of the space of maximal free line segments among $n$ balls of unit or arbitrary radii. This closes the problem of bounding the complexity of this space for balls and it improves on the previously known $\Omega(n^3)$ lower bound for balls of arbitrary radii and on the trivial $\Omega(n^2)$ bound for unit balls. This result also settles negatively the natural conjecture that this space of free line segments has smaller worst-case complexity for disjoint fat objects than for skinny triangles.

We also proved an $\Omega(n^3)$ lower bound on the worst-case combinatorial complexity of the space of free lines among $n$ balls of arbitrary radii, improving over the trivial $\Omega(n^2)$ bound. This bound almost matches the upper bound of $O(n^{3+\epsilon})$ from [24] and essentially closes the problem of determining tight worst-case bounds on the complexity of the space of free lines among balls of arbitrary radii. On the other hand, the case of unit balls (Problem 61 of The Open Problems Project [11]) remains open with a complexity between $\Omega(n^2)$ and $O(n^{3+\epsilon})$.

# Acknowledgments

The authors wish to thank Olivier Devillers and Jeff Erickson for fruitful discussions on this topic.

# 5. REFERENCES

[1] P. K. Agarwal, B. Aronov, V. Koltun, and M. Sharir. Lines avoiding unit balls in three dimensions. *Discrete Comput. Geom.*, 34(2):231–250, 2005.

[2] P. K. Agarwal, B. Aronov, and M. Sharir. Line transversals of balls and smallest enclosing cylinders in three dimensions. *Discrete and Computational Geometry*, 21:373–388, 1999.

[3] P. K. Agarwal and M. Sharir. Davenport-Schinzel sequences and their geometric applications. In J.-R. Sack and J. Urrutia, editors, *Handbook of Computational Geometry*. North-Holland, 1998.

[4] C. Borcea, X. Goaoc, S. Lazard, and S. Petitjean. Common tangents to spheres in $\mathbb{R}^3$. *Discrete and Computational Geometry*, 35(2):287–300, 2006.

[5] H. Brönnimann, O. Devillers, V. Dujmovic, H. Everett, M. Glisse, X. Goaoc, S. Lazard, H. Na, and S. Whitesides. Lines and free line segments tangent to arbitrary three-dimensional convex polyhedra. *SIAM Journal on Computing*, 37(2):522–551, 2007.

[6] H. Brönnimann, O. Devillers, S. Lazard, and F. Sottile. Lines tangent to four triangles in three-dimensional space. *Discrete and Computational Geometry*, 37(3):369–380, 2007.

[7] H. Brönnimann, H. Everett, S. Lazard, F. Sottile, and S. Whitesides. Transversals to line segments in three-dimensional space. *Discrete and Computational Geometry*, 34(3):381–390, 2005.

[8] B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, and J. Stolfi. Lines in space: combinatorics and algorithms. *Algorithmica*, 15:428–447, 1996.

[9] R. Cole and M. Sharir. Visibility problems for polyhedral terrains. *Journal of Symbolic Computation*, 7(1):11–30, 1989.

[10] M. de Berg, H. Everett, and L. Guibas. The union of moving polygonal pseudodiscs – combinatorial bounds and applications. *Computational Geometry: Theory and Applications*, 11:69–82, 1998.

[11] E. Demaine, J. Mitchell, and J. O'Rourke. The Open Problems Project – problem 61. http://maven.smith.edu/~orourke/TOPP/P61.html.

[12] J. Demouth, O. Devillers, H. Everett, M. Glisse, S. Lazard, and R. Seidel. On the complexity of umbra and penumbra. *Computational Geometry: Theory and Applications*, 42(8):758–771, 2009.

[13] O. Devillers, V. Dujmovic, H. Everett, X. Goaoc, S. Lazard, H.-S. Na, and S. Petitjean. The expected number of 3D visibility events is linear. *SIAM Journal on Computing*, 32(6):1586–1620, 2003.

[14] F. Durand. A multidisciplinary survey of visibility, 2000. ACM Siggraph course notes, Visibility, Problems, Techniques, and Applications. http://people.csail.mit.edu/fredo/PUBLI/surv.pdf.

[15] F. Durand, G. Drettakis, and C. Puech. The 3D visibility complex. *ACM Transactions on Graphics*, 21(2):176–206, 2002.

[16] A. Efrat, L. J. Guibas, O. A. Hall-Holt, and L. Zhang.
On incremental rendering of silhouette maps of a
polyhedral scene. *Computational Geometry, Theory
and Applications*, 38(3):129–138, 2007.

[17] D. Halperin and M. Sharir. New bounds for lower envelopes in three dimensions, with applications to visibility in terrains. *Discrete and Computational Geometry*, 12:313–326, 1994.

[18] H. Kaplan, N. Rubin, and M. Sharir. Line transversals of convex polyhedra in $\mathbb{R}^3$. In *20th Annual ACM-SIAM Symposium on Discrete Algorithms - SODA '09*, pages 170–179, 2009.

[19] I. Macdonald, J. Pach, and T. Theobald. Common tangents to four unit balls in $\mathbb{R}^3$. *Discrete and Computational Geometry*, 26(1):1–17, 2001.

[20] G. Megyesi and F. Sottile. The envelope of lines meeting a fixed line and tangent to two spheres. *Discrete and Computational Geometry*, 33(4):617–644, 2005.

[21] G. Megyesi, F. Sottile, and T. Theobald. Common transversals and tangents to two lines and two quadrics in $\mathbb{P}^3$. *Discrete and Computational Geometry*, 30(4):543–571, 2003.

[22] M. Pellegrini. On lines missing polyhedral sets in 3-space. *Discrete and Computational Geometry*, 12:203–221, 1994.

[23] M. Pocchiola and G. Vegter. The visibility complex. *Internat. J. Comput. Geom. Appl.*, 6(3):279–308, 1996.

[24] N. Rubin. Lines avoiding balls in three dimensions revisited. In *26th Annual ACM Symposium on Computational Geometry - SCG'10*, 2010.