Hervé Brönnimann

Olivier Devillers
email: olivier.devillers@inria.fr.

Vida Dujmovi Ć §

Hazel Everett

Marc Glisse

Xavier Goaoc

SYLVAIN LAZARD ¶ Hyeon-Suk Na

AND Sue Whitesides

S Lazard

LINES AND FREE LINE SEGMENTS TANGENT TO ARBITRARY THREE-DIMENSIONAL CONVEX POLYHEDRA *

Keywords: Computational geometry, 3D visibility, visibility complex, visual events AMS subject classifications. 65D18, 68U05

Motivated by visibility problems in three dimensions, we investigate the complexity and construction of the set of tangent lines in a scene of three-dimensional polyhedra. We prove that the set of lines tangent to four possibly intersecting convex polyhedra in R 3 with a total of n edges consists of Θ(n 2 ) connected components in the worst case. In the generic case, each connected component is a single line, but our result still holds for arbitrarily degenerate scenes. More generally, we show that a set of k possibly intersecting convex polyhedra with a total of n edges admits, in the worst case, Θ(n 2 k 2 ) connected components of maximal free line segments tangent to at least four polytopes. Furthermore, these bounds also hold for possibly occluded lines rather than maximal free line segments.

Finally, we present a O(n 2 k 2 log n) time and O(nk 2 ) space algorithm that, given a scene of k possibly intersecting convex polyhedra, computes all the minimal free line segments that are tangent to any four of the polytopes and are isolated transversals to the set of edges they intersect; in particular, we compute at least one line segment per connected component of tangent lines.

Introduction.

Computing visibility relations in a 3D environment is a problem central to computer graphics and engineering tasks such as radio propagation simulation and fast prototyping. Examples of visibility computations include determining the view from a given point, and computing the umbra and penumbra cast by a light source. 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 [START_REF] Durand | A multidisciplinary survey of visibility[END_REF] for a survey).

One such structure, the visibility complex [START_REF] Durand | The 3D visibility complex[END_REF][START_REF] Pocchiola | The visibility complex[END_REF], encodes visibility relations by partitioning the set of maximal free line segments. The size of this partition is intimately related to the number of maximal free line segments tangent to four objects in the scene; for a scene of n triangles in R 3 , the complex can have size Θ(n 4 ) in the worst case [START_REF] Durand | The 3D visibility complex[END_REF], even when the triangles form a terrain (see [START_REF] Cole | Visibility problems for polyhedral terrains[END_REF] or Figure 1.1). The complex is thus potentially enormous, which has hindered its application in practice. However, there is evidence, both theoretical and practical, that this estimation is pessimistic. The lower bound examples, which are carefully designed to exhibit the worst-case behavior, are unrealistic in practice. For realistic scenes, Durand et al. [START_REF] Durand | The visibility skeleton: a powerful and efficient multi-purpose global visibility tool[END_REF] observe a quadratic growth rate, albeit for rather small scenes. For random scenes, Devillers et al. [START_REF] Devillers | The expected number of 3D visibility events is linear[END_REF] prove that the expected size of the visibility complex is much smaller; for uniformly distributed unit balls the expected size is linear and for polygons or polyhedra of bounded aspect ratio and similar size it is at most quadratic. Also, in 2D, while the worst-case complexity of the visibility complex is quadratic, experimental re-FIG. 1.1. A terrain of size n with Ω(n 4 ) maximal free line segments tangent in four points.

sults strongly suggest that the size of the visibility complex of a scene consisting of scattered triangles is linear [START_REF] Cho | Interactive ray tracing with the visibility complex, Computers and Graphics[END_REF].

While these results are encouraging, most scenes are not random. In fact, most scenes have a lot of structure which we can exploit; a scene is typically represented by many triangles which form a much smaller number of convex patches. In particular, if a scene consists of k disjoint convex polyhedra with a total of n edges, then under a strong general position assumption, the number of maximal free line segments tangent to four of the polyhedra is at most O(n2 k 2 ); this follows directly from the bound proved in [START_REF] Efrat | On Incremental Rendering of Silhouette Maps of a Polyhedral Scene[END_REF] on the number of combinatorial changes of the silhouette map viewed from a point moving along a straight line, and was also later proved in [START_REF] Brönnimann | On the Number of Lines Tangent to Four Convex Polyhedra[END_REF]. We present in this paper a generalization of these results. After preliminary definitions, we give a detailed account of our results and then present related previous work.

Preliminary definitions. We consider a scene that consists of a finite number of polytopes, not necessarily disjoint, not necessarily fully dimensional, and in arbitrary position. The definitions below are standard, yet carefully phrased in a way that remains valid in those situations.

A polytope is the convex hull of a point set. A plane is tangent to a polytope if it intersects the polytope and bounds a closed half-space that contains the polytope. A face, an edge, or a vertex of a polytope in R 3 is the 2, 1 or 0-dimensional intersection of the polytope with a tangent plane. Note that, with this usual definition of polytopes, edges and faces are closed and they are not subdivided in any way.

A line or segment is tangent to a polytope (whether or not the latter is fully dimensional) if it intersects the polytope and is contained in a tangent plane. In a given plane, a line is tangent to a polygon if it intersects the polygon and bounds a closed half-plane that contains the polygon. With these definitions, given a polygon in a plane π, and a line contained in π that intersects the relative interior of this polygon, the line is tangent to the polygon when considered as a polytope in R 3 , but not tangent to the polygon in the plane π.

The set of lines in R 3 has a natural topological structure, namely, that of Plücker space [START_REF] Stolfi | Oriented Projective Geometry: A Framework for Geometric Computations[END_REF]. The set of lines tangent to at least four polytopes is a subspace, whose connected components correspond to lines that can be continuously moved one into the other while remaining tangent to at least four polytopes. 1 A line or line segment is free if it is tangent to each polytope that its relative interior intersects; 2 otherwise it is occluded. A free line segment is a maximal free line segment if it is not properly contained into another free line segment. The space of line segments also has a natural topological structure and the connected components of maximal free line segments tangent to at least four among the k polytopes are defined similarly as for lines.

A support vertex of a line is a polytope vertex that lies on the line. A support edge of a line is a polytope edge that intersects the line but has no endpoint on it (a support edge intersects the line at only one point of its relative interior). A support of a line is one of its support vertices or support edges. The supports of a segment are defined similarly. Notice that it follows from the definition of polytopes that any line has at most two supports in any given polytope.

A line is isolated with respect to a set of edges and vertices if the line cannot be moved continuously while remaining a common transversal to these edges and vertices. Furthermore, we say that a set S of edges and vertices admits an isolated transversal if these edges and vertices admit a common transversal that is isolated with respect to S. Finally, a line is isolated if it is isolated with respect to a set of some, and hence all, of its supports.

Our results. In this paper we present two types of results, combinatorial bounds and algorithms.

Combinatorial bounds. We generalize the result of [START_REF] Brönnimann | On the Number of Lines Tangent to Four Convex Polyhedra[END_REF][START_REF] Efrat | On Incremental Rendering of Silhouette Maps of a Polyhedral Scene[END_REF] in two ways. First, we consider polytopes that may intersect. We show that among k polytopes of total complexity n, the number of lines tangent to any four of them is in the worst case either infinite or Θ(n 2 k 2 ). The most surprising aspect of this result is that the bound (which is tight) is the same whether the polytopes intersect or not. This is in sharp contrast to the 2D case, where the number of tangents of two convex polygons is always 4 if disjoint, and could be linear in the size of the polygons if they intersect. Second, we consider polytopes in arbitrary position: we drop all general position assumptions. The polytopes may intersect in any way; they may overlap or coincide. They may degenerate to polygons, segments or points. While four polytopes in general position (as defined in [START_REF] Brönnimann | On the Number of Lines Tangent to Four Convex Polyhedra[END_REF]) admit a finite number of common tangents, four polytopes in arbitrary position may admit an infinite number of common tangents which can be partitioned into connected components.

Our main results are, more precisely, the following. THEOREM 1.1. Given k polytopes in R 3 with n edges in total, there are, in the worst case, Θ(n 2 k 2 ) connected components of maximal free line segments tangent to at least four of the polytopes. This bound also holds for connected components of possibly occluded lines tangent to at least four of the polytopes.

These results improve the trivial bound of O(n 4 ). Note that, when k = 4, neither of the two results stated in Theorem 1.1 implies the other since a line tangent to at least four among k polytopes may contain many, but does not necessarily contain any, maximal free line segments tangent to four polytopes.

When k = 4, Theorem 1.1 implies that there are Θ(n 2 ) connected components of lines tangent to the four polytopes, an improvement on the previously known upper bound of O(n 3 log n) which follows from the same bound on the complexity of the set of line transversals to a set of polyhedra (here four) with n edges in total [START_REF] Agarwal | On stabbing lines for convex polyhedra in 3D[END_REF]. Moreover, we prove a tighter bound when one of the four polytopes has few edges. THEOREM 1.2. Given 3 polytopes with n edges in total and one polytope with m edges, there are, in the worst case, Θ(mn) connected components of lines tangent to the four polytopes.

We also prove the following result which is more powerful, though more technical, than Theorem 1.1. Whereas Theorem 1.1 bounds the number of connected components of tangents, Theorem 1.3 bounds the number of isolated tangents with some notion of multiplicity. For example, the line in Figure 1.2 is counted k 2 times which is the number of minimal sets of vertices that admit that line as an isolated transversal. Although neither theorem implies the other, we will prove in Proposition 3.4 that the upper bound of Theorem 1.1 is easily proved using Theorem 1.3. THEOREM 1.3. Given k polytopes in R 3 with n edges in total, there are, in the worst case, Θ(n 2 k 2 ) minimal sets of open edges and vertices, chosen from some of the polytopes, that admit a possibly occluded isolated transversal that is tangent to these polytopes.

Algorithm. We now turn our attention to the computation of all free segments that are isolated transversals to their set of supports and tangent to the corresponding polytopes. Durand et al. [START_REF] Durand | The 3D visibility complex[END_REF] proposed an algorithm for this problem with worst-case time complexity O((n 3 + p) log n) where p is the output size; this algorithm, based on a double-sweep, has proven to be difficult to implement. Durand et al. also presented an algorithm with Θ(n 5 ) worst-case time complexity that incorporates interesting heuristics leading to reasonable performance in practice [START_REF] Durand | The visibility skeleton: a powerful and efficient multi-purpose global visibility tool[END_REF]. We present an algorithm that uses, in the worst case, O(n 2 k 2 log n) time and O(nk 2 ) space, is readily implementable, and uses only simple data structures. The polytopes may intersect and be in arbitrary position. A preliminary version of this algorithm was described for disjoint convex polyhedra in X. Goaoc's Ph.D. thesis [START_REF] Goaoc | Structures de visibilité globales : taille, calcul et dégénérescences[END_REF].

THEOREM 1.4. Given k polytopes in R 3 with n edges in total, we can compute, in O(n 2 k 2 log n) time and O(nk) space, all the possibly occluded lines that are isolated transversals to their set of supports and tangent to the corresponding polytopes. We can also compute, in O(n 2 k 2 log n) time and O(nk 2 ) space, all the minimal free segments that are isolated transversals to their set of supports and tangent to the corresponding polytopes.

It should be noted that our algorithm does not provide the endpoints (possibly at infinity) of the maximal free segments. Computing the endpoints of each such segment can be done by shooting rays in O(log 2 n) time per ray using O((nk) 2+ε ) preprocessing time and storage [START_REF] Agarwal | Ray shooting among convex polytopes in 3D[END_REF]. Such ray-shooting data structures are not, however, readily implementable. Alternatively, each ray-shooting query can be answered in O(k log n) time after O(n log n) preprocessing time and using additional O(n) space by applying the Dobkin-Kirkpatrick hierarchy on each polytope [START_REF] Dobkin | Fast detection of polyhedral intersection[END_REF].

To emphasize the importance of considering intersecting polytopes, observe that computer graphics scenes often contain non-convex objects. These objects, however, can be decomposed into sets of convex polyhedra. Notice that simply decomposing these objects into convex polyhedra with disjoint interiors may induce a scene of much higher complexity than a decomposition into intersecting polytopes. Moreover, the decomposition of a polyhedron into interior-disjoint polytopes may introduce new tangents which were not present in the original scene; indeed a line tangent to two polytopes along a shared face is not tangent to their union.

Worst-case

Expected free lines to a polyhedron Θ(n 4 ) (trivial) free lines above a polyhedral terrain

O(n 3 2 c √ log n ) [20, 22] free lines among disjoint homothetic polytopes Ω(n 3 ) [4]
free lines among unit balls Ω(n 2 ) [START_REF] Devillers | The expected number of 3D visibility events is linear[END_REF], O(n 3+ε ) [2] Θ(n) [START_REF] Devillers | The expected number of 3D visibility events is linear[END_REF] max. free segments above a polyhedral terrain Θ(n 4 ) [11] isolated maximal free segments among k generic disjoint convex polyhedra Θ(n 2 k 2 ) [START_REF] Efrat | On Incremental Rendering of Silhouette Maps of a Polyhedral Scene[END_REF][START_REF] Brönnimann | On the Number of Lines Tangent to Four Convex Polyhedra[END_REF] max. free segments among unit balls Ω(n 2 ) [START_REF] Devillers | The expected number of 3D visibility events is linear[END_REF], O(n 4 ) Θ(n) [START_REF] Devillers | The expected number of 3D visibility events is linear[END_REF] TABLE 1.1 Published bounds on the complexity of the set of free lines or maximal free line segments among objects of total complexity n. The expected complexities are given for the uniform distribution of the balls centers.

The importance of considering polytopes in arbitrary position comes from the fact that graphics scenes are full of degeneracies both in the sense that four polytopes may admit infinitely many tangents and that polytopes may share edges or faces. There may actually be more connected components of tangents when the objects are in degenerate position; this is, for instance, the case for line segments [START_REF] Brönnimann | Transversals to line segments in three-dimensional space[END_REF]. Also, we could not find a perturbation argument that guarantees the preservation of all (or at least a constant fraction of) the connected components of tangents and we do not believe that finding such a perturbation is a simple matter.

Related results.

Previous results on this topic include those that bound the complexity of sets of free lines or free line segments among different sets of objects. They are summarized in Table 1.1.

Recently, Agarwal et al. [START_REF] Agarwal | Lines avoiding unit balls in three dimensions[END_REF] proved that the set of free lines among n unit balls has complexity O(n 3+ε ). Devillers et al. showed a simple bound of Ω(n 2 ) [START_REF] Devillers | The expected number of 3D visibility events is linear[END_REF] for this problem, and Koltun recently sketched a bound of Ω(n 3 ) (personal communication, 2004).

The complexity of the set of free line segments among n balls is trivially O(n 4 ). Devillers and Ramos showed that the set of free line segments can have complexity Ω(n 3 ) (personal communication 2001, see also [START_REF] Devillers | The expected number of 3D visibility events is linear[END_REF]). When the balls are unit size, the Ω(n 2 ) lower bound for the set of free lines holds. A lower bound of Ω(n 4 ) that applies to either case was recently sketched by Glisse (personal communication, 2004).

We mention two results for polyhedral environments. Halperin and Sharir [START_REF] Sharir | New Bounds for Lower Envelopes in Three Dimensions, with Applications to Visbility in Terrains[END_REF] and Pellegrini [START_REF] Pellegrini | On lines missing polyhedral sets in 3-space[END_REF] proved that, in a polyhedral terrain with n edges, the set of free lines has near-cubic complexity. De Berg, Everett and Guibas [START_REF] Berg | The union of moving polygonal pseudodiscs -Combinatorial bounds and applications[END_REF] showed a Ω(n 3 ) lower bound on the complexity of the set of free lines (and thus free segments) among n disjoint homothetic convex polyhedra.

This paper is organized as follows. We prove the upper bounds of Theorems 1.1, 1.2, and 1.3 in Sections 2 and 3, and the lower bounds in Section 4. In section 5, we present our algorithm for computing free segments.

Main lemma.

We prove in this section a lemma which is fundamental for the proofs of the upper bounds of Theorems 1.1, 1.2, and 1.3. Consider four polytopes P, Q, R, and S in R 3 , with p, q, r, and s 1 edges, respectively, and let e be an edge of S.

MAIN LEMMA. There are O(p + q + r) isolated lines intersecting e and tangent to P, Q, R and S excluding those that lie in planes that contain e and are tangent to all four polytopes.

The proof of the Main Lemma is rather complicated because it handles polytopes which may intersect as well as all the degenerate cases. To assist the reader, we first give an overview of the proof. We then state preliminaries and definitions in Section 2.2. In Sections 2.3 and 2.4, we bound the number of so-called "generic tangent lines". In Section 2.5, we bound the number of "non-generic tangent lines". Finally, in Section 2.6, we pull these results together to conclude the proof of the Main Lemma.

Proof overview.

The proof is inspired by a method which was, to our knowledge, first used in [START_REF] Bern | Visibility with a moving point of view[END_REF] (and later in [START_REF] Berg | Sparse arrangements and the number of views of polyhedral scenes[END_REF][START_REF] Efrat | On Incremental Rendering of Silhouette Maps of a Polyhedral Scene[END_REF][START_REF] Brönnimann | On the Number of Lines Tangent to Four Convex Polyhedra[END_REF]). We present here an overview of the proof in which we do not address most of the problems arising from degeneracies. In particular, some definitions and remarks will require more elaboration in the context of the complete proof.

We sweep the space with a plane Π t rotating about the line containing e. The sweep plane intersects the three polytopes P, Q, and R in three, possibly degenerate or empty, convex polygons denoted P t , Q t , and R t , respectively (see Figure 2.1). During the sweep, we track the bitangents, that is, the lines tangent to P t and Q t , or to Q t and R t , in Π t . As the sweep plane rotates, the three polygons deform and the bitangents move accordingly. Every time two bitangents become aligned during the sweep, the common line they form is tangent to P, Q, and R.

In any given instance of the sweep plane Π t , we consider the pairs of bitangents (one involving P t and Q t , and the other Q t and R t ) that share a vertex of Q t (see Figure 2.1). The isolated lines intersecting e and tangent to P, Q, R and S are isolated transversals with respect to a tuple of supports that consists of e and the supports of two such bitangents. We consider all candidate such tuples of supports as the sweep plane rotates.

Such a tuple induced by an instance of the sweep plane changes as the plane rotates only when a support of a bitangent changes. We define critical planes in such a way that the supports of the bitangents do not change as the sweep plane rotates between two consecutive critical planes. As the sweep plane rotates, the supports of a bitangent change if a support starts or ceases to be swept, or if, during its motion, the bitangent becomes tangent to one of the polygons along an edge of that polygon (see Figure 2.2). In the latter case, this means that the bitangent crosses a face or contains an edge of one of the polytopes. We thus define two types of critical planes: an instance of the sweep plane is critical if it contains a vertex of one of the polytopes, or if it contains a line that lies in the plane containing a face of one of the polytopes, and is tangent to another of the polytopes (see Figures 2.2 and 2.3). We will show that the number of critical planes is O(p + q + r).

When the polytopes intersect there may exist a linear number of bitangents in an instance of the sweep plane (two intersecting convex polygons may admit a linear number of bitangents, as is the case for two regular n-gons where one is a rotation of the other about its center). Thus there can be a linear number of candidate tuples induced by any instance of the sweep plane, and the linear number of critical planes leads to a quadratic bound on the

Π t-ε Π t+ε Π t Q t+ε P t+ε P t-ε P t Q t-ε Q t e e e

FIG. 2.2.

A bitangent to P t and Q t is tangent to P t along an edge. The plane Π t is F-critical.

total number of distinct candidate tuples. In the detailed proof of the lemma, we amortize the count of candidate tuples over all the critical planes to get a linear bound on the number of distinct candidate tuples and thus on the number of isolated lines intersecting e and tangent to P, Q, R and S; this bound will however not hold for those isolated lines that lie in planes that contain e and are tangent to all four polytopes. Indeed, the number of such isolated tangent lines can be quadratic, in degenerate cases; for instance, four polytopes such that a plane contains edge e and a face of linear complexity from each other polytope may admit in this plane a quadratic number of such isolated tangent lines (one through each of a quadratic number of pairs of vertices).

Preliminaries and definitions.

We can assume without loss of generality that P, Q, R and S have non-empty interior. Indeed, since the set of isolated tangent lines to the four polytopes is zero-dimensional, there is always room to extend any polytope with empty interior in such a way that none of the original isolated tangent lines are lost.

We say that a line properly intersects a polygon if it intersects its relative interior. In the sequel, we use this definition only when the line and polygon are coplanar. Notice that a line that contains a segment is tangent to the segment as well as properly intersects it.

Let l e be the line containing e and let Π t denote the sweep plane parameterized by t ∈ [0, π] such that Π t contains the line l e for all t and Π 0 = Π π . Each plane Π t intersects the three polytopes P, Q, and R in three, possibly degenerate or empty, convex polygons, P t , Q t , and R t , respectively (see Figure 2.1).

For any t, a bitangent to polygons P t and Q t is a line tangent to P t and Q t in Π t (the line may intersect the polygon R t in any way, possibly not at all). For any t, let a (P t , Q t )-tuple be the unordered set of all supports in P and Q of one of the bitangents to polygons P t and Q t . Note that a support in P may be identical to a support in Q, in which case the (P t , Q t )-tuple does not contain duplicates. Also note that a (P t , Q t )-tuple consists of exactly one support in P and one support in Q (possibly identical) except when the corresponding bitangent is tangent to P (or Q) along a face (either intersecting the face properly or containing one of its edges); then the (P t , Q t )-tuple contains two supports in P (or Q) instead of one. A PQ-tuple is a set of edges and vertices that is a (P t , Q t )-tuple for some t. We define similarly the (Q t , R t )-tuples and QR-tuples.

We say that a (P t , Q t )-tuple is maximal for some t if it is not contained in any other (P t , Q t )-tuple, for the same t. Note that a (P t , Q t )-tuple is non-maximal for some t if and only if all its supports intersect Π t in one and the same point, and P t and Q t are not equal to one and the same point (see Figure 2.5(b)).

Q P P t R t Π t Q ∩ Ψ Q t e
For any t, let a (P t , Q t , R t )-tuple be the union of a (P t , Q t )-tuple and a (Q t , R t )-tuple that share at least one support in Q. A (P t , Q t , R t )-tuple is maximal for some t if it is not contained in any other (P t , Q t , R t )-tuple, for the same t. A PQR-tuple is a set of edges and vertices that is a (P t , Q t , R t )-tuple for some t. Note that a PQR-tuple typically consists of three supports, one from each polytope, and consists, in all cases, of at most two supports in P, at most three supports in Q, and at most two supports in R.

A line intersecting e and tangent to P, Q, R and S is called a generic tangent line if and only if it intersects S only on e and is tangent to P t , Q t , and R t in some plane Π t . Otherwise it is called a non-generic tangent line. A non-generic tangent line properly intersects a face of S or properly intersects P t , Q t , or R t in some plane Π t . In the latter case P t , Q t , or R t is a face or an edge of P, Q, or R lying in Π t ; thus a non-generic tangent line is (in both cases) tangent to P, Q, R and S in a plane containing a face or two edges of these polytopes, a degenerate situation.

In the following three subsections, we bound the number of generic and non-generic tangent lines. It is helpful to keep in mind that, as observed earlier, two convex polygons in a plane Π t (such as P t and Q t ) may admit a linear number of tangents if they intersect.

Generic tangent lines.

LEMMA 2.1. The set of supports in P, Q, and R of a generic tangent line is a PQRtuple.

Proof. Any generic tangent line is tangent in Π t to P t , Q t , and R t for some value t. Thus the set of supports of in P and

Q (resp. in Q and R) is a (P t , Q t )-tuple (resp. a (Q t , R t )- tuple)
. Moreover the (P t , Q t )-tuple and the (Q t , R t )-tuple contain the same supports in Q, and thus their union is a (P t , Q t , R t )-tuple, hence a PQR-tuple.

We now define the critical planes Π t in such a way that, as we will later prove, the set of (P t , Q t , R t )-tuples is invariant for t ranging strictly between two consecutive critical values. We introduce two types of critical planes: the V-critical and F-critical planes.

A plane Π t is V-critical if it contains a vertex of P, Q, or R, not on l e . (The constraint that the vertex does not lie on l e ensures that the number of V-critical planes is finite even in degenerate configurations.) A plane Π t is F-critical relative to an ordered pair of polytopes (P, Q) if (see Figure 2.3) it contains a line such that

Ψ m = Π t * ∩ Ψ Π t * +ε ∩ Ψ Π t * -ε ∩ Ψ edge of Q in Ψ face of P in Π t * Π t * l e m = Π t * ∩ Ψ Q t * P t * Π t * -ε l e Π t * -ε ∩ Ψ Q t * -ε P t * -ε Π t * +ε l e Π t * +ε ∩ Ψ Q t * +ε P t * +ε edge of P edge of P l e face of P in Ψ FIG. 2.4
. Plane Π t * contains a line m such that (i) m lies in a plane Ψ = Π t * containing a face of P, and (ii) m is tangent to polygon P ∩ Ψ at some point not on l e ; however m is not tangent to Q ∩ Ψ. If the definition of F-critical planes was not considering such plane Π t * to be F-critical then Lemma 2.3 would not hold. Indeed the set u of supports of line Π t * -ε ∩ Ψ is a maximal (P t , Q t )-tuple for some but not all t in any open neighborhood of t * , and, although Π t * is V-critical, there exists no V-critical event (t * , v) such that u contains v or an edge with endpoint v.

(i) lies in a plane Ψ = Π t containing a face of P, and (ii) is tangent in Ψ to polygon Q ∩ Ψ or P ∩ Ψ, at some point not on l e . For simplicity, we do not require that is tangent to P; this leads to overestimating the number of common tangents to P, Q, R, and S but only by an asymptotically negligible amount. Note that not all lines in Ψ tangent to Q are tangent to the polygon Q ∩ Ψ when that polygon is a face or edge of Q lying in Ψ. Note also that we define Π t to be F-critical when is tangent to P ∩ Ψ at some point not on l e only for handling the very degenerate case where Q ∩ Ψ is an edge of Q and there exists a line in Ψ that properly intersects Q ∩ Ψ and is tangent to P ∩ Ψ along an edge that has an endpoint on l e (see Figure 2.4). Note finally that if ∈ Π t satisfies (i) and is tangent, in Ψ, to P ∩ Ψ at some point not on l e then polytope Q plays no role and thus Π t is F-critical relative to (P, Q) for all polytopes Q.

F-critical planes relative to (Q, P), (Q, R), and (R,

Q) are defined similarly. A plane Π t is F-critical if it is F-critical relative to pairs of polytopes (P, Q), (Q, P), (Q, R), or (R, Q).
The values of t corresponding to critical planes Π t are called critical values. We call V-critical and F-critical events the ordered pairs (t, o) where t is a critical value and o is a vertex or line depending on the type of critical event. In a V-critical event, o is a vertex of P, Q, or R that belongs to Π t \ l e . In an F-critical event, o is a line lying in some plane Π t and satisfying Conditions (i-ii) above. A critical event is a V-critical or F-critical event. LEMMA 2.2. There are at most 2 3 (p + q + r) V-critical events and 8 3 (p + 2 q + r) Fcritical events.

Proof. The number of V-critical events is at most the total number of vertices of P, Q, and R, and hence is less than two thirds the total number of edges of P, Q, and R. We now count the number of F-critical events relative to polytopes (P, Q). Let Ψ be a plane containing a face of P, and suppose that for some plane Π t , line = Π t ∩ Ψ satisfies Conditions (i-ii). Plane Ψ does not contain l e because otherwise both l e and lie in the two distinct planes Ψ and Π t , so = l e but then cannot satisfy Condition (ii). Furthermore and l e intersect or are parallel since they both lie in Π t . Thus if Ψ ∩ l e is a point then contains it, and otherwise Ψ ∩ l e = / 0 and is parallel to l e .

If Ψ ∩ l e is a point, there are at most four candidates for a line in plane Ψ going through Ψ ∩ l e and tangent to Q ∩ Ψ or P ∩ Ψ at some point not on l e . Likewise, if Ψ ∩ l e is empty, there are at most four candidates for a line in plane Ψ that is parallel to l e and tangent to Q ∩ Ψ or P ∩ Ψ. In either case, each candidate line is contained in a unique plane Π t , for t ∈ [0, π], since = l e ( contains a point not on l e ). Hence, a face of P generates at most four F-critical events relative to (P, Q). Therefore the number of critical events relative to (P, Q) is at most 8 3 p since the number of faces of a polytope is at most two thirds the number of its edges. Hence the number of critical events relative to (P, Q), (Q, P), (Q, R) and (R, Q) is at most 8 3 (p + 2 q + r).

The following lemma states that the critical planes have the desired property. Let u e be the set of supports of l e in P and Q and let u denote some (P t , Q t )-tuple.

LEMMA 2.3. Let t * be the endpoint of a maximal interval3 throughout which u = u e is a maximal (P t , Q t )-tuple. Then t * is a critical value. Moreover, there exists a V-critical event (t * , v) or a F-critical event (t * , m) such that u contains v or an edge with endpoint v, or u is contained in the set of supports of m.

The proof of this lemma is rather long and intricate; we postpone it to Section 2.4. Note that, as stated, this lemma only applies under the assumptions that u is maximal and distinct from u e . These assumptions are made in order to simplify the proof of Lemma 2.3; we don't suggest that the lemma is false without them.

LEMMA 2.4. Any edge or vertex of P or Q is in at most 2 PQ-tuples that are maximal (P t , Q t )-tuples for all t in any given non-empty interval 3 of R/πZ.

Proof. Let t be an element of a non-empty interval I of R/πZ and x be an edge or vertex of P or Q. If x does not intersect Π t then no (P t , Q t )-tuple contains x. If x intersects Π t in one point then there are, in general, at most two lines in Π t going through x and tangent to P t and Q t (see Figure 2.5(a)); in all cases there are at most 3 (P t , Q t )-tuples containing x (see Figure 2.5(b)), however at most 2 of them are maximal. If x intersects Π t in more than one point, x is an edge lying in Π t . Then any line in Π t intersecting x and tangent to P t and Q t contains an endpoint of x and thus x belongs to no (P t , Q t )-tuple.

Hence at most 2 PQ-tuples contain x and are maximal (P t , Q t )-tuples for t = t, and thus at most 2 PQ-tuples contain x and are maximal (P t , Q t )-tuples for all t in I . LEMMA 2.5. There are at most O(p + q + r) PQR-tuples. Proof. In order to count the number of distinct (P t , Q t , R t )-tuples, we charge each maximal (P t , Q t , R t )-tuple to a critical event. We then show that each critical event is charged at most a constant number of times. It then follows from Lemma 2.2 that there are O(p + q + r) distinct maximal (P t , Q t , R t )-tuples. A maximal (P t , Q t , R t )-tuple consists of at most two supports in P, at most three supports in Q, and at most two supports in R, and thus contains at most (2 2 -1)(2 3 -1)(2 2 -1) distinct subsets with at least one support in each of P, Q and R. Each maximal (P t , Q t , R t )-tuple thus contains at most a constant number of distinct (P t , Q t , R t )-tuples, which implies the result.

Let s be a maximal (P t , Q t , R t )-tuple and let I be any maximal connected subset of R/πZ such that s is a maximal (P t , Q t , R t )-tuple for all t ∈ I . Let u be a maximal (P t , Q t )-tuple and u a maximal (Q t , R t )-tuple such that the union of u and u is s and such that u and u share at least one support in Q.

First, suppose that I = R/πZ. Then u is a maximal (P t , Q t )-tuple for all t ∈ R/πZ. Thus each support in u intersects Π t for all t ∈ R/πZ and thus intersects l e ; moreover each support in u intersects Π t only on l e for all t ∈ R/πZ except possibly for one value of t. Since P and Q have non-empty interior, P t ∪ Q t is not reduced to a point for all t in some interval of positive length. For all t in such an interval, since u is maximal, the union of the supports in u intersects Π t in at least two distinct points. These at least two distinct points lie on l e for some values of t by the above argument. Thus, for these values of t, l e is the only line in Π t whose set of supports contains u. Hence u is the set of supports of l e . The same property holds for v and thus s is also the set of supports of l e . We can thus assume in the following that I = R/πZ, and only count the maximal (P t , Q t , R t )-tuples that are not the set of supports of l e .

Interval I is thus a non-empty interval of R/πZ; it can be open or closed, a single point or an interval of positive length. Let w 0 and w 1 denote the endpoints of I = R /πZ.

If s contains a vertex v, or an edge with endpoint v, such that v lies in Π w i \ l e , for i = 0 or 1, then we charge s to the V-critical event (w i , v). Otherwise, we charge s to an F-critical event (w i , m) where m is a line in Π w i whose set of supports contains u or u . Such a V-critical or F-critical event exists by Lemma 2.3.

We now prove that each critical event is charged by at most a constant number of distinct maximal (P t , Q t , R t )-tuples. As mentioned before, that will imply the result.

Consider a V-critical event (t * , v) that is charged by a maximal (P t , Q t , R t )-tuple s. By the charging scheme, s contains a support x that is v or an edge with endpoint v, and s is a maximal (P t , Q t , R t )-tuple for all t in at least one of three intervals, {t * } and two open intervals having t * as endpoint; denote these intervals by I 1 , I 2 , I 3 . By Lemma 2.4, at most 2 PQ-tuples contain x and are maximal (P t , Q t )-tuples for all t in I i . Moreover, each of these PQ-tuples contains at most 2 supports in Q, and each of these supports belongs to at most 2 QR-tuples that are maximal (Q t , R t )-tuples for all t in I i . Thus at most 8 PQR-tuples contain x and are maximal (P t , Q t , R t )-tuples for all t in I i , for each i = 1, . . . , 3. Hence any V-critical event (t * , v) is charged by at most 24 distinct maximal (P t , Q t , R t )-tuples.

Consider now an F-critical event (t * , m) that is charged by a maximal (P t , Q t , R t )-tuple s, and define as before u and u . By the charging scheme, the set of supports of m contains u or u (or both); suppose without loss of generality that it contains u. The set of supports of m contains at most two supports in P and at most two supports in Q. Since u contains at least one support in P and at least one support in Q, there are at most 3 2 choices for u.

By the charging scheme, s is a maximal (P t , Q t , R t )-tuple for all t in at least one of 3 intervals, {t * } and two open intervals having t * as endpoint; denote by I 1 , I 2 , I 3 these intervals.

It follows from Lemma 2.4 that, for each support x of Q in u, at most 2 QR-tuples contain x and are maximal (Q t , R t )-tuples for all t in I i . There are at most 3 2 choices for u (as shown above), 2 for x, 3 for i and 2 for the QR-tuples containing x. Hence any F-critical event (t * , m) is charged by at most 2 2 × 3 3 distinct maximal (P t , Q t , R t )-tuples.

Therefore each critical event is charged by at most a constant number of distinct maximal (P t , Q t , R t )-tuples, which concludes the proof.

COROLLARY 2.6. There are at most O(p + q) PQ-tuples.

Proof. Replace R by a copy of Q in Lemma 2.5. Any PQ-tuple is also a PQQ-tuple, and there are at most O(p + q + q) = O(p + q) of these.

PROPOSITION 2.7. There are O(p + q + r) isolated generic tangent lines. Proof. A generic tangent line is transversal to e and to the edges and vertices of a PQRtuple, by definition and Lemma 2.1. An isolated generic tangent line is thus an isolated transversal with respect to a set of edges and vertices that consists of a PQR-tuple and either edge e or one or both of its endpoints. The number of such sets is four times the number of PQR-tuples, which is in O(p + q + r) by Lemma 2.5. The result follows since each such set consists of at most eight edges and vertices (at most two supports from each of the four polytopes) and thus admits at most eight isolated transversals [START_REF] Brönnimann | Transversals to line segments in three-dimensional space[END_REF].

Proof of Lemma 2.3.

Recall that u e denotes the set of supports of l e in P and Q, and that Lemma 2.3 states the following.

Let t * be the endpoint of a maximal interval throughout which u = u e is a maximal (P t , Q t )-tuple. Then t * is a critical value. Moreover, there exists a V-critical event (t * , v) or a F-critical event (t * , m) such that u contains v or an edge with endpoint v, or u is contained in the set of supports of m. We can assume that u contains no vertex v and no edge with endpoint v, such that v lies on Π t * \ l e because otherwise (t * , v) is a V-critical event such that u contains v or an edge with endpoint v, which concludes the proof.

We prove a series of lemmas that yields Lemma 2.3. Indeed, we prove the existence of a line m in Π t * whose set of supports contains u (Lemma 2.10) such that (i) m lies in a plane Ψ = Π t * containing a face of P (Lemma 2.11), and (ii) m is tangent in Ψ to polygon Q ∩ Ψ or P ∩ Ψ, at some point not on l e (Lemma 2.12). This proves that Π t * contains a line m whose set of supports contains u and such that (t * , m) is an F-critical event, which concludes the proof.

By hypothesis, for any sufficiently small open neighborhood N of t * whose endpoints are denoted by t 0 and t 1 , u is not a maximal (P t , Q t )-tuple for some t ∈ N and u is a maximal (P t , Q t )-tuple for t = t * or for all t ∈ (t * ,t 1 ) (or by symmetry for all t ∈ (t 0 ,t * )).

We only consider in the following supports in P and in Q; polytope R plays no role. We start by proving two preliminary lemmas.

LEMMA 2.8. Each support in u intersects Π t in exactly one point (possibly on l e ), for all t in any sufficiently small open neighborhood N of t * .

Moreover, the union of all supports in u intersects Π t in at least two distinct points for all t = t * in N . This property also holds for t = t * if u is a maximal

(P t * , Q t * )-tuple.
Proof. Since u is a (P t , Q t )-tuple for some t in every open neighborhood of t * , each support in u intersects Π t for some t in every open neighborhood of t * . It thus follows from the assumption that u contains no vertex v and no edge with endpoint v, such that v lies on Π t * \l e , that each support in u intersects Π t for all t in any sufficiently small open neighborhood N of t * . It follows that each support in u either lies in l e or intersects Π t in exactly one point for all t ∈ N . However, no edge of u lies in l e because otherwise, if x denotes such an edge of, say, P, then any line tangent to P t in Π t and intersecting x contains an endpoint of x which is a vertex of P; thus, by definition, u does not contain x but one of its endpoints. Hence each support of u intersects Π t in exactly one point for all t ∈ N . We now prove that the union of the supports in u intersects Π t in at least two distinct points for any t ∈ N such that u is a maximal (P t , Q t )-tuple. Suppose for a contradiction that the union of the supports in u intersects Π t in one single point v for some t ∈ N such that u is a maximal (P t , Q t )-tuple. Then polygons P t and Q t are both reduced to point v because otherwise u is not maximal (otherwise, a line in Π t tangent to P t and Q t at v can be rotated about v until it becomes tangent to P t or Q t at some other points). Thus v = P t = Q t is a vertex of P and of Q because the polytopes have non-empty interior. Hence u = {v} because each support in u contains v. It follows that v lies on l e since each support in u intersects Π t for all t ∈ N . Moreover, since P t and Q t are both reduced to point v = l e ∩ P = l e ∩ Q, the set u e of supports of l e is u, contradicting the hypotheses of Lemma 2.3.

Thus, if u is a maximal (P t , Q t )-tuple for all t ∈ (t * ,t 1 ), the union of the supports in u intersects Π t in at least two distinct points for all t ∈ (t * ,t 1 ) and thus for all t = t * in any sufficiently small open neighborhood of t * . Also, if u is a maximal (P t , Q t )-tuple for t = t * , the union of the supports in u intersects Π t in at least two distinct points for t = t * and thus for all t in any sufficiently small open neighborhood of t * . LEMMA 2.9. If u is a maximal (P t * , Q t * )-tuple then u consists of at least three supports.

Proof. Note that it follows from Lemma 2.8 that u contains at least two supports. Suppose for a contradiction that u consists of only two supports. By Lemma 2.8, they intersect Π t in exactly two distinct points for all t in any sufficiently small open neighborhood N of t * . Thus there exists for all t ∈ N a unique line m t in Π t whose set of supports contains u; moreover m t is continuous in terms of t. Since u is a maximal (P t * , Q t * )-tuple, the set of supports of m t * is u. Thus, for all t in any sufficiently small N , the set of supports of m t is u. Thus the set of supports of m t is invariant for t ∈ N and since m t * is tangent to P t * and Q t * , line m t is tangent to P t and Q t for all t ∈ N .

Hence, for all t ∈ N , line m t , whose set of supports is u, is tangent to P t and Q t in Π t . Thus u is a maximal (P t , Q t )-tuple for all t ∈ N . Moreover, m t is the unique line in Π t whose set of supports contains u, thus u is a maximal (P t , Q t )-tuple for all t ∈ N , contradicting the hypotheses of the lemma.

LEMMA 2.10. There exists a line m in Π t * whose set of supports contains u that is tangent to P t * and Q t * along an edge of one of them, say of P t * .

Proof. Consider first the case where u is a maximal (P t * , Q t * )-tuple. There exists in Π t * a line m tangent to P t * and Q t * whose set of supports is u. By Lemma 2.9, the set u of supports of m contains at least three supports, and hence at least two supports in P (or in Q). Furthermore, the supports of m in one polytope intersect Π t * in distinct points (by definition of supports). Thus m intersects P t * (or Q t * ) in at least two distinct points and is tangent to P t * and Q t * . The result follows since P t * (and Q t * ) is convex.

Consider now the case where u is a maximal (P t , Q t )-tuple for all t ∈ (t * ,t 1 ). Then, for all t ∈ (t * ,t 1 ), there exists a line in Π t tangent to P t and Q t and whose set of supports is u. Moreover, by Lemma 2.8, this line is unique for each t ∈ (t * ,t 1 ) and varies continuously in terms of t ∈ (t * ,t 1 ). When t tends to t * , the line tends to a line m t * in Π t * which is tangent to P t * and Q t * and whose set of supports contains u. If its set of supports strictly contains u then m t * is tangent to P t * and Q t * along an edge of one of them because the polygons are convex, and hence we can choose m = m t * to complete the proof. Otherwise, u is a (P t * , Q t * )-tuple.

We can suppose that u is a non-maximal (P t * , Q t * )-tuple since we already treated the case where u is maximal. There exists in Π t * a line tangent to P t * and Q t * whose set of supports is u. Since u is non-maximal this line is tangent to P t * and Q t * at a shared vertex, and can be rotated about this vertex in Π t * until it becomes tangent to P t * and Q t * at some other points,

Π t * m = Π t * ∩ Ψ P t * l e face of P in Ψ Q t * FIG. 2.6. Line m is tangent to P along a face in plane Ψ = Π t * .
which must occur because u is non-maximal; let m denote the resulting line. The set of supports of m contains u and m is tangent to P t * and Q t * along an edge of one of them because the polygons are convex.

LEMMA 2.11. Line m lies in a plane Ψ = Π t * containing a face of P.

Proof. By Lemma 2.10, m contains an edge of P t * ; see Figure 2.6. This edge either intersects the relative interior of some face of P in which case we take Ψ to be the plane containing that face, or it is an edge of P in which case we take Ψ to be a plane, different from Π t * , containing one of the two faces of P incident to that edge. Let m t be the line Ψ ∩ Π t for all t in any sufficiently small open neighborhood N of t * ; line m t is well defined since Ψ ∩ Π t * is line m by Lemmas 2.10 and 2.11.

LEMMA 2.12. Line m is tangent to P ∩ Ψ or to Q ∩ Ψ, at some point not on l e . Proof. We assume for a contradiction that line m does not satisfy the lemma, i.e., m is not tangent to P ∩ Ψ or to Q ∩ Ψ at any point other than on l e . We prove that the set of supports of m is u and is a maximal (P t , Q t )-tuple for all t in any sufficiently small neighborhood of t * , contradicting the hypotheses of Lemma 2.3 and thus proving Lemma 2.12.

Since m is tangent to Q (by Lemma 2.10), m is tangent to Q ∩ Ψ only on l e (see Fig- 4 . Similarly m is tangent to P ∩ Ψ only on l e , or m properly intersects it; however P ∩ Ψ is necessarily a face of P by Lemma 2.11.

The following Lemmas 2. [START_REF] Dobkin | Fast detection of polyhedral intersection[END_REF] lies on m by Lemma 2.10 and thus lies in plane Ψ by Lemma 2.11. Hence, for all t ∈ N , the support vertices in u lie on m t , and thus are supports of m t .

Ψ m = Π t * ∩ Ψ Π t * +ε ∩ Ψ Π t * -ε ∩ Ψ l e face of P in Ψ face of Q in Ψ (a) (b) Ψ m = Π t * ∩ Ψ Π t * +ε ∩ Ψ Π t * -ε ∩ Ψ Q ∩ Ψ
In order to prove that the support edges in u are supports of m t , it is sufficient (by Lemma 2.10) to prove that the support edges of m are supports of m t . The support edges of m in P lie in plane Ψ (see Figure 2.7(b)) because Ψ contains m and a face of P (indeed if m intersects an edge of P not in Ψ then m contains one of its endpoints, and thus the edge is not a support). Thus all the support edges of m lie in Ψ and m contains none of their endpoints (by definition). Since m t lies in Ψ for all t and m t * = m, line m t intersects all the support edges of m and contains none of their endpoints for all t in any sufficiently small open neighborhood N of t * . Hence the support edges of m in P are supports of m t for all t ∈ N .

Consider the case where Q ∩ Ψ is a face or an edge of Q. Similarly as for P, the support edges of m in Q lie in plane Ψ, and thus are supports of m t for all t ∈ N . Consider now the case where m is tangent to Q ∩ Ψ only on l e at, say, point v (see Figure 2.7(a)). Then v lies in Ψ (since m ⊂ Ψ by Lemma 2.11) and also lies in Π t for all t (since l e ⊂ Π t for all t). Hence m t contains v for all t ∈ N . Moreover, m t is tangent to Q ∩ Ψ only at v for all t in any sufficiently small open neighborhood N of t * . Hence the set of supports of m t in Q is invariant for all t ∈ N .

We have so far proved that the set of supports of m t contains u for all t ∈ N . We now prove that the set of supports of m t is u for some t ∈ N . Consider first the case where u is a maximal (P t * , Q t * )-tuple. Then, by Lemma 2.8, the union of the supports in u intersects Π t * in at least two distinct points, thus m t * = m is the only line in Π t * whose set of supports contains u. Moreover, since u is a (P t * , Q t * )-tuple, there exists a line in Π t * whose set of supports is u. Hence the set of supports of m t * is u. Consider now the case where u is a maximal (P t , Q t )-tuple for all t ∈ (t * ,t 1 ). By Lemma 2.8, for all t ∈ (t * ,t 1 ), the union of the supports in u intersects Π t in at least two distinct points, thus m t is the only line in Π t whose set of supports contains u. For all t ∈ (t * ,t 1 ), since u is a (P t , Q t )-tuple there exists a line in Π t whose set of supports is u. Hence the set of supports of m t is u for all t ∈ (t * ,t 1 ).

LEMMA 2.

The set of supports of m t is invariant for t ranging in any sufficiently

small open neighborhood N of t * . Proof. First if m = l e then m t = l e for all t ∈ N because Ψ contains m = l e (by Lemma 2.11) and Π t contains l e for all t (by definition). Thus the set of supports of m t is invariant for all t ∈ N . We now assume that m = l e .

Line m is tangent to polygon P t * along an edge by Lemma 2.10. Thus m is tangent to P in at least two points. Hence, since P ∩ Ψ is a face of P and m lies in Ψ, either m properly intersects P ∩ Ψ or m is tangent to P ∩ Ψ along one of its edges. In the later case, the edge does not lie in l e since m = l e , thus m is tangent to P ∩ Ψ at some point not on l e , contradicting our assumptions. Hence m properly intersects the face of P in Ψ.

It follows that, if m contains a vertex of P, then this vertex is an endpoint of a support edge of m t for all t in any sufficiently small open neighborhood of t * (indeed m t lies in Ψ and tends to m when t tends to t * ). By Lemma 2.13, the set of supports of m t is u for some t in any sufficiently small open neighborhood of t * . Hence, if m contains a vertex of P, this vertex is an endpoint of a support edge in u. By assumption u contains no edge with endpoint on Π t * \ l e , thus m contains no vertex of P except possibly on l e (since m lies in Π t * ). It thus follows that the set of supports of m t in P is invariant for t ranging in any sufficiently small open neighborhood of t * (since m t ⊂ Ψ tends to m when t tends to t * and all supports of m lie in Ψ).

Now consider the case where m properly intersects Q ∩ Ψ which is a face or an edge of Q. Similarly as for P, m contains no vertex of Q except possibly on l e and thus the set of supports of m t in Q is invariant for t ranging in any sufficiently small open neighborhood of t * .

Finally, consider the case where m is tangent to Q ∩ Ψ only on l e . Then, as in the proof of Lemma 2.13, the set of supports of m t in Q is invariant for all t ranging in any sufficiently small open neighborhood of t * , which concludes the proof.

Non-generic tangent lines.

We count here the number of non-generic tangent lines. Note that, as mentioned before, there are no such lines under some adequate general position assumption.

PROPOSITION 2.15. There are at most O(p + q + r) isolated non-generic tangent lines except possibly for those that lie in planes that contain e and are tangent to all four polytopes.

Proof. An isolated non-generic tangent line lies in plane Π t for some t and contains (at least) two distinct points, each of which is a vertex of P, Q, R, or S, or a point of tangency between the line and one of the polygons P t , Q t , and R t ; indeed, otherwise the line can be moved in Π t while keeping the same supports.

We count first the isolated non-generic tangent lines that contain two distinct points of tangency with two of the polygons P t , Q t , and R t in Π t for some t. Consider such a line tangent to, say, P t and Q t in Π t . Line is non-generic and thus properly intersects a face of S or a face or an edge of R lying in Π t . If properly intersects a face of S or a face or an edge of R lying in Π t but not entirely contained in l e , then Π t is one of the at most four planes tangent to R or S. There are O(p + q) lines tangent to P t and Q t in two distinct points in each of these planes and thus O(p + q) such lines in total. Otherwise, Π t intersects each of R and S in an edge contained in l e . The supports of are thus the union of a PQ-tuple, and of, in each of R and S, the edge lying in l e or one (or both) of its endpoint. It follows that at most a constant number of such isolated non-generic tangent lines contain a given PQ-tuple in its set of supports. Hence the number of such lines is at most the number of PQ-tuples, which is in O(p + q) by Corollary 2.6. It follows that there are at most O(p + q + r) isolated non-generic tangent lines that contain two distinct points of tangency with two of the polygons P t , Q t , and R t in Π t for some t. We obtain similarly that there are at most O(p + q + r) isolated nongeneric tangent lines that contain two distinct points of tangency with only one the polygons P t , Q t , and R t .

We now count the isolated non-generic tangent lines that contain a unique vertex of P, Q, R, or S and a unique point of tangency with the polygons P t , Q t , and R t in Π t for some t. Each vertex v of P, Q, R, or S that does not lie on l e is contained in a unique plane Π t and there are, in that plane, at most six lines through v and tangent to P t , Q t , or R t . There are thus O(p + q + r) such lines in total. Consider now a line through a vertex v on l e and tangent to P t at w = v in Π t for some t. We can suppose that each of Q t and R t is either tangent to at w or is properly intersected by ; indeed otherwise is tangent to two polygons in two distinct points. If Q t (or R t ) is a face of Q (resp. R) or an edge not contained in l e then Π t is one of the at most two planes tangent to Q (resp. R) and, in each of these planes, there are at most two lines through v and tangent to P t . If Q t (or R t ) is tangent to at w such that the support edges of in P and in Q (resp. R) are not collinear then goes through a vertex of P, Q, R, or S that lies on l e , and through a vertex of the intersection of two of these polytopes. There are at most eight vertices of P, Q, R, and S on l e and O(p + q + r) vertices on the intersection of two of these polytopes. There are thus O(p + q + r) such lines in total. Otherwise, Q t (and R t ) is an edge contained in l e or is tangent to at w such that the support edges of in P and in Q (resp. R) are collinear; then is not isolated.

We finally bound the number of isolated non-generic tangent lines that contain no point of tangency with the polygons P t , Q t , and R t in Π t for any t (and thus contain at least two vertices of P, Q, R, and S). Consider such a line that lies in plane Π t for some t. Line is tangent to P, Q, and R and thus properly intersect P t , Q t , and R t in plane Π t which is tangent to P, Q, and R. If plane Π t is not tangent to S, goes through an endpoint of e (since is tangent to S) and there are O(p + q + r) such lines that go through an endpoint of e and at least another vertex of P, Q, or R. If plane Π t is tangent to S, line lies in a plane Π t tangent to P, Q, R, and S, which concludes the proof.

Note that there can be Ω(n 2 ) isolated non-generic tangent lines that lie in a plane tangent to all four polytopes. Consider, for instance, four polytopes that admit a common tangent plane containing edge e, an edge e of P, and two faces of Q and R of linear complexity such that all the lines through a vertex of each face intersect e and e . All these lines are isolated non-generic tangent lines.

Proof of the Main

Lemma. Proposition 2.7, which handles the isolated generic tangent lines, and Proposition 2.15, which handles the isolated non-generic tangent lines, directly yield the Main Lemma.

Upper bounds.

We prove in this section the upper bounds of Theorems 1.1, 1.2, and 1.3. The lower bounds are proved in Section 4. Consider k pairwise distinct polytopes P 1 ,. . . , P k with n 1 ,. . . , n k edges, respectively, and n edges in total.

LEMMA 3.1. For any edge e of P i , there are O(n j + n l + n m ) sets of open edges, chosen from P i , P j , P l , and P m , that admit an isolated transversal that intersects e and is tangent to these four polytopes.

Proof. Any isolated transversal to a set of edges is isolated with respect to the set of all its supports. It is thus sufficient to bound the number of sets of open edges, chosen from P i , P j , P l , and P m , that are intersected by an isolated line that intersects e and is tangent to these four polytopes. The Main Lemma states that there are O(n j + n l + n m ) isolated lines intersecting e and tangent to P i , P j , P l , and P m , excluding those that lie in planes that contain e and are tangent to all four polytopes. Any of these O(n j + n l + n m ) isolated lines intersects at most two open edges in any polytope. Thus there are O(n j + n l + n m ) sets of open edges (chosen from P i , P j , P l , and P m ) that are intersected by one of these isolated lines. Now consider any isolated line that lies in a plane that contains e and is tangent to all four polytopes. This plane contains all the open edges that are intersected by the isolated line. Thus these edges (and any subset of them) admit no isolated transversal. LEMMA 3.

A minimal set of open edges and vertices that admit an isolated transversal consists of (i) two vertices, (ii) one vertex and one or two edges, or (iii) two, three, or four edges.

Proof. Consider a minimal set of open edges and vertices that admits an isolated transversal. The elements are necessarily distinct because the set is minimal. If the set contains two vertices, it contains no other element since the two vertices admit a unique transversal. Suppose now that the set contains one vertex. None of the open edges contain the vertex because otherwise such an edge would be redundant. Thus, the vertex and any segment define either a line, and thus admit an isolated transversal, or they define a plane. If none of the other edges intersect that plane in a unique point, the vertex and all open edges admit zero or infinitely many common transversals, a contradiction. Thus there exists an edge that intersects the plane in a unique point. Hence, the vertex and two open edges admit a unique transversal, and the minimal set contains no other element.

Suppose finally that the set only contains open edges. The characterization of the transversals to a set of line segments [START_REF] Brönnimann | Transversals to line segments in three-dimensional space[END_REF] shows that either two, three or four of these line segments admit at most two transversals, or that the set of common transversals to all the open line segments can be parameterized by an open set of parameters in R 2 , R or R/πZ. In the latter case, the edges admit no isolated transversal, a contradiction. Hence, the minimal set of edges consists of two, three or four edges. (Note that two or three edges may admit an isolated transversal if that transversal contains one or two of the edges.)

We can now prove the upper bound of Theorem 1.3. PROPOSITION 3.3. There are O(n 2 k 2 ) minimal sets of open edges and vertices, chosen from some polytopes, that admit an isolated transversal that is tangent to these polytopes.

Proof. We bound the number of minimal sets depending of their type according to Lemma 3.2. First, there are O(n 2 ) pairs of vertices, pairs of edges, and sets of one vertex and one edge. Hence, at most O(n 2 ) such pairs admit an isolated transversal.

Consider a minimal set of one vertex and two open edges, chosen from some polytopes, that admit an isolated transversal that is tangent to these polytopes. The open edges do not contain the vertex because otherwise they admit no isolated transversal. Thus the vertex and each edge define a plane. For each of the O(n 2 ) planes defined by a vertex and an open edge not containing it, there are O(k) lines in that plane that are tangent to one of the polytopes at some point other than the vertex. Hence there are O(n 2 k) sets of one vertex and two edges, chosen from some polytopes, that admit an isolated transversal that is tangent to these polytopes.

It is straightforward to show that three open edges admit an isolated transversal only if the line containing one of the edges intersects the two other edges. Since any line intersects at most two open edges in any of the k polytopes, there are O(nk 2 ) sets of three open edges that admit an isolated transversal.

Consider now the case of four edges, chosen from at most three polytopes, that admit an isolated transversal that is tangent to these polytopes. The two edges chosen from the same polytope belong to the same face, and the isolated transversal lies in the plane containing that face. Each of the two other open edges intersects that plane in one point, because otherwise the four open edges admit zero or infinitely many transversals. For each of the O(n) planes containing a face of one of the polytopes, and each of the O(n) edges intersecting that plane in exactly one point, there are at most 2k lines in that plane that contain this point and are tangent to one of the k polytopes at some other point. Hence there are O(n 2 k) sets of four open edges, chosen from at most three polytopes, that admit an isolated transversal that is tangent to these polytopes.

We finally bound the number of sets of four edges, no two chosen from the same polytope. By Lemma 3.1 and by summing over all n edges e of the polytopes, the number T of sets of four open edges, chosen from four polytopes, that admits an isolated transversal that is tangent to these four polytopes satisfies

T n ∑ j<l<m C (n j + n l + n m ),
where C is some constant. Since each n i , 1 i k, appears k-1 2 times in the sum, it follows that

T C n ∑ 1 i k n i k -1 2 = C n 2 k -1 2 so T is in O(n 2 k 2 ) as claimed.
The above result implies the following upper bounds and in particular those of Theorem 1.1.

PROPOSITION 3.4. There are O(n 2 k 2 ) connected components of maximal free line segments tangent to at least four of the polytopes. This bound also holds for connected components of possibly occluded lines tangent to at least four of the polytopes. Furthermore, the same bound holds for isolated such segments or lines.

Proof. We prove the proposition for possibly occluded lines tangent to at least four of the polytopes; the proof is similar for maximal free line segments. By Proposition 3.3, there are O(n 2 k 2 ) minimal sets of open edges and vertices, chosen from some polytopes, that admit an isolated transversal that is tangent to these polytopes. The bound on the number of connected components thus follows from the fact that any connected component of lines tangent to four polytopes contains an isolated line. Indeed, any non-isolated line can be moved while keeping the same set of supports until (at the limit) the line intersects a new edge or vertex. During the motion, the line remains tangent to all four polytopes since it keeps the same supports (except at the limit); if the line has more than one degree of freedom, this can be repeated until the line becomes isolated.

We now prove the upper bound of Theorem 1.2. We start by two preliminary lemmas. LEMMA 3.5. Four possibly intersecting convex polygons in R 2 admit at most a constant number of connected components of line transversals.

Proof. Consider the usual geometric transform where a line in R 2 with equation y = ax + b is mapped to the point (-a, b) in the dual space (see e.g. [24, §8.2.1]). The transversals to a convex polygon are mapped to a region bounded from above by a convex x-monotone curve and from below by a concave x-monotone curve; such a region is called stabbing region, and the curves are referred to as the upper and lower boundaries of the stabbing region. The transversals to four polygons are mapped to the intersection of four stabbing regions. There exists no transversal of a given slope if and only if the lower boundary of a stabbing region lies above the upper boundary of another stabbing region at that slope. Two such boundaries intersect in at most two points, and thus the transversals to four polygons form at most a constant number of connected components of transversals.

As in Section 2, let P, Q, R, and S be four polytopes in R 3 , with p, q, r, and s 1 edges, respectively, and let e be a closed edge of S.

LEMMA 3.6. There are O(p + q + r) connected components of lines intersecting e and tangent to P, Q, R and S.

Proof. As in the proof of Proposition 3.4, any connected component of lines intersecting e and tangent to P, Q, R, and S contains an isolated line. The Main Lemma thus yields that there are O(p + q + r) connected components of lines intersecting e and tangent to P, Q, R and S except for the components that only contain isolated lines that lie in planes that contain e and are tangent to all four polytopes.

We show that there are at most a constant number of connected components of lines intersecting e and tangent to P, Q, R and S that lie in planes that contain e and are tangent to all four polytopes. There may be infinitely many such planes that intersect P, Q, R and S only on l e but all the lines tangent to the four polytopes in all these planes belong to the same connected component. Besides these planes there are at most two planes containing e and tangent to all four polytopes. In any such plane, the lines tangent to the four polytopes are the transversals to the four polygons that are the faces, edges, or vertices of P, Q, R, and S lying in the plane. Lemma 3.5 thus yields the result.

We can now prove the upper bound of Theorem 1.2. PROPOSITION 3.7. Given 3 polytopes with n edges in total and one polytope with m edges, there are O(mn) connected components of lines tangent to the four polytopes.

Proof. Let S denote the polytope with m edges. First, if S consists of a single point, it is straightforward to show that there are O(n) connected components of lines tangent to the four polytopes. Otherwise, by summing over all the edges of S, Proposition 3.6 yields that the number of connected components of lines tangent to the four polytopes is O(mn).

Lower bounds.

We provide in this section the lower-bound examples needed for Theorems 1.1, 1.2, and 1.3. The following proposition proves the lower bound of Theorem 1.2.

LEMMA 4.1. There exist four disjoint polytopes of complexity n such that the number of common tangent lines is finite and Ω(n 2 ). There also exist two polytopes of complexity n and two polytopes of complexity m such that the number of common tangent lines is finite and Ω(mn).

Proof. We consider four planar regular polygons P, Q, R, and S, each with n vertices, embedded in R 3 . P is centered at the origin and parallel to the yz-plane, Q is obtained from P by a rotation of angle π n about the x-axis, and R and S are obtained from P and Q, respectively, by a translation of length 1 in the positive x-direction (see Figure 4.1). We transform the polygons P and Q into the polytopes P and Q by adding a vertex at coordinates (ε, 0, 0). Similarly, we transform the polygons R and S into the polytopes R and S by adding a vertex at coordinates (1 + ε, 0, 0).

For ε sufficiently small, the lines tangent to P, Q, R and S are the lines through a vertex of P ∩ Q and a vertex of R ∩ S. Since P ∩ Q and R ∩ S have 2n vertices each, there are 4n 2 tangent lines. Now, moving P and S by 2ε in the x direction ensures the disjointness of the polytopes while preserving the existence of the tangents if ε is small enough.

Replacing R and S in the above construction by regular polygons each with m vertices yields the Ω(mn) lower bound in the case of two polytopes of complexity n and two polytopes of complexity m.

We now prove the lower bounds of Theorems 1.1 and 1.3. The following proposition directly yields these bounds since the number of isolated tangents to any four of the polytopes is less or equal to the number of sets of open edges and vertices in at most four polytopes that admit an isolated transversal that is tangent to these polytopes. LEMMA 4.2. There exist k disjoint polytopes of total complexity n such that the number of maximal free line segments tangent to four of them is finite and Ω(n 2 k 2 ). Moreover these segments lie in pairwise distinct lines.

Proof. The lower bound example is similar to the one with four polyhedra. For simplicity suppose that n and k are such that n k and k 4 are integers. We first take a n k -regular polygon A 1 in the plane x = 0. Next we consider a copy, B 0 , of A 1 scaled by a factor of (1 + ε), and on each edge of B 0 we place k 4 points. Polygon B i , 1 i k 4 , is constructed by taking the i th point on each edge of B 0 . If ε is small enough, the intersection points of A 1 and B i are outside the other polygons B j for 1 j k 4 and i = j. Now the A i , for 2 i k 4 , are constructed as copies of A 1 scaled by a factor 1 + i k ε Figure 4.1). For the moment, all polygons lie in plane x = 0. We now construct 4 families of k 4 polygons each: -P i is a copy of A i translated by iε in the negative x direction -Q i is a copy of B i translated by iε in the positive x direction -R i is a copy of B i translated by 1iε in the positive x direction -S i is a copy of A i translated by 1 + iε in the positive x direction Any choice of four polygons, one in each family P i , Q j , R l and S m , reproduces the quadratic example of Lemma 4.1 with polygons of size n k and thus with total number of tangents larger than k

4 4 4 n k 2 = n 2 k 2 4
. Furthermore the lines tangent to P i , Q j , R l and S m are only occluded by P i and S m for i > i and m > m, that is, beyond the portion of the tangents containing the contact points. The k polygons can be transformed into k convex polyhedra as in Lemma 4.1.

Algorithm.

Using the sweep-plane algorithm outlined in Section 2.1, we can compute in O(n 2 k 2 log n) time all minimal sets of open edges and vertices, chosen from some of the polytopes, that admit a possibly occluded isolated transversal that is tangent to these polytopes. Now, for some of these lines, the segment joining the contact points with the polytopes is free. We can use standard, but complicated, ray-shooting data structures in order to determine which of these O(n 2 k 2 ) segments are free; this can be done in O(log 2 n)-time per query using O((nk) 2+ε ) preprocessing time and storage [START_REF] Agarwal | Ray shooting among convex polytopes in 3D[END_REF].

We present in this section a solution that uses O(n 2 k 2 log n) time and O(nk 2 ) space. We adapt the algorithm outlined in Section 2.1 to directly compute the minimal sets of edges and vertices admitting an isolated line transversal that contains a free segment tangent to their respective polytopes. Our algorithm has better time and space complexities than the previously mentioned approach, and is readily implementable. Moreover, the space complexity drops to O(nk) if no occlusion is taken into account. Precisely, we prove the following theorem which is more powerful, though more technical, than Theorem 1.4 and directly yields it. THEOREM 5.1. Given k polytopes in R 3 with n edges in total, we can compute in O(n 2 k 2 log n) time and O(nk) space all the minimal sets of open edges and vertices, chosen from some of the polytopes, that admit an isolated, possibly occluded, line transversal tangent to these polytopes. We can also compute, in O(n 2 k 2 log n) time and O(nk 2 ) space, all the minimal sets of open edges and vertices that admit an isolated line transversal containing a maximal free segment that is tangent to these polytopes. Furthermore, the algorithm reports which of the transversals contains such a free line segment.

For ease of presentation, we describe a simplified version of the algorithm in which we assume that the polytopes are in generic position; see Section 5.2 for details. Using the same techniques as in Section 2, it is straightforward though tedious to generalize the algorithm for arbitrary situations. We also only detail the algorithm for the case of minimal sets of four edges, no two chosen from the same polytope; the other sets of at most four edges and vertices can be computed similarly.

Algorithm overview and data structures.

The input to our algorithm is a set of possibly intersecting polytopes structured in a standard way so that classic incidence queries can be performed in constant time (see, for instance, [7, §9.1]).

We consider each polytope edge, e, in turn and sweep a plane around it between its two incident faces. During the sweep we create and maintain the following objects.

Combinatorial polygons. The sweep plane intersects each polytope in a (possibly empty) convex polygon whose vertices correspond to polytope edges. For each of these polygons, we maintain the set of vertices, each represented by its corresponding polytope edge, in a data structure that admits logarithmic-time vertex insertion, deletion and look-up operations, as well as ray-shooting queries. This can be done with a balanced binary search tree (see [21, §7.9.1]).

Combinatorial bitangents. The algorithm keeps track of the lines contained in the sweep plane and tangent to two polygons. The polytopes properly intersected by such a bitangent between its two supports are its blockers. A bitangent is represented by (pointers to) its two supports and a set of its blockers, ordered by polytope index, stored in a balanced binary search tree.

Polytope edges. We associate with each polytope edge a list of pointers to the combinatorial bitangents it supports in the current sweep plane.

Critical events. The sweep stops at critical events at which time combinatorial polygons and bitangents are updated. In addition to the V-and F-critical events defined in Section 2.3, we introduce the following two new types of events at which the set of blockers of some combinatorial bitangents may change. A T-critical event occurs whenever three bitangents, supported by a PQR-tuple, become aligned (see Figure 5.1b). An I-critical event occurs when the sweep plane contains a point of intersection between an edge and a face of two (distinct) polytopes (see Figure 5.2). Each event is represented by a data structure providing pointers to the primitives that define it: a vertex for a V-event, a bitangent and a face for a F-event, three bitangents for a T-event, and a face and an edge for a I-event. In addition, for a T-event, we store a bit of information specifying which of the line transversals to l e and the three support edges defines the T-event. Note that the critical value of each critical event can be computed in constant time from the information associated with the event; it thus does not need to be explicitly stored.

Finally, critical events are sorted in the order in which they appear during the sweep and stored in an event queue supporting insertion and deletion in logarithmic time.

Generic position assumption.

Our generic position assumption is that the ordered set of events does not change under any arbitrarily small perturbation of the input polytopes. This assumption corresponds to (i) the events are generic, and (ii) no two events occur in the same sweep plane, except for F-and I-critical events induced by the same pair of edge and face. The genericity of the events is ensured by (but not characterized by) the following geometric conditions:

V-critical events: no vertex lies on a line containing another edge, F-critical events: no two edges in two distinct polytopes are coplanar, I-critical events: if an edge intersects a face of another polytope, it does so properly and not on a line containing another edge, T-critical events: any four lines containing polytope edges admit zero or two transversals.

Initialization.

For each new sweep, we initialize the event queue and construct the combinatorial polygons and combinatorial bitangents as follows.

Combinatorial polygons. Computing the combinatorial polygons in the initial sweep plane can easily be done in O(n) time.

Combinatorial bitangents. The bitangent lines to two polygons P and Q in the initial sweep plane through a given vertex of P can be computed by a binary search on Q in O(log n) time. The blockers of a given bitangent can be found using one ray-shooting query per combinatorial polygon, for a total time of O(k log n). Altogether, the O(nk) combinatorial bitangents can thus be computed in O(nk 2 log n) time.

Event queue. There are O(n) V-critical events and O(nk) I-critical events, since an edge intersects a polytope in at most two faces. The O(nk) edge-face intersection points are computed and stored once before the beginning of the first sweep; this computation can be done by using brute force in O(n 2 ) time, and with O(nk) space, since it is done once for all the sweeps. For each sweep, all the V-and I-critical events can then be inserted in O(nk log n) time. For each of the O(nk) combinatorial bitangents, we also insert F-and T-critical events in O(k log n) time as explained in Section 5.4 (Lemma 5.2). In total, initializing the event queue takes O(nk 2 log n) time per sweep.

Thus, initializing all the combinatorial polygons, bitangents, and the event queue can be done in O(nk 2 log n) time per sweep plus O(n 2 ) time overhead for a total of O(n 2 k 2 log n) time as announced in Theorem 5.1.

Updating the event queue.

Every time a new combinatorial bitangent is created, we compute and insert into the queue new F-and T-events as described below. Let e 1 and e 2 denote the two support edges of a new combinatorial bitangent. Let Π t 0 denote the critical plane at which the new combinatorial bitangent is created.

New T-critical events. See Figure 5.1a-b. Consider all the bitangents having e 1 as support edge and compute the set of support edges (distinct from e 1 and e 2 ) of all these bitangents.

Compute the intersection of this set with the similar set for e 2 ; this can be done in O(k log k) time by ordering the edges by their indices. For each edge e 3 in that set, insert a T-event for each line transversal to l e , e 1 , e 2 , and e 3 if the transversal is tangent to the three polytopes containing e 1 , e 2 , and e 3 ; this test can be done in constant time. Each of the at most k insertions into the event queue takes O(log n). Thus computing and inserting the new T-critical events takes O(k log n) time per new bitangent.

New F-critical events. Consider in turn each of the four faces incident to one of the two support edges. Let e 1 and f denote the considered edge and face. We compute a candidate F-event, in constant time, as follows. Compute the line (if any) that lies in the plane Ψ containing f and goes through l e and e 2 (see Figure 5.1c). If is tangent to the polytope containing e 2 , defines an F-event. We reject this F-event if does not intersect e 1 (in such a case, the edge e 1 does not intersect the sweep plane at the F-event and thus the combinatorial bitangent to e 1 and e 2 would have been deleted at some V-event before the F-event). We also discard this F-event if it occurs at the critical value t 0 where the (considered) bitangent is created (that is Π t 0 contains ); we discard such F-events because when a bitangent is created at an F-event, we do not re-insert the same F-event into the queue. We thus retain at most four F-events, at most one for each of the four faces incident to one of the two support edges. If no F-event is retained, the bitangent will be deleted at a V-critical event and no new F-critical event is created. If more than one F-event is retained, we need only keep the first one, since, as we shall see in Section 5.5.2, the combinatorial bitangent will be deleted at the first of these events.

Again, let f denote the face incident to edge e 1 that induces that F-critical event. If the other support edge, e 2 , intersects face f (see Figure 5.1d), then this event will be treated as an I-critical event and again we create no new F-event. Otherwise, we insert the F-event into the queue in O(log n) time. We thus get the following lemma.

LEMMA 5.2. Each time a combinatorial bitangent is created, the event queue can be updated in O(k log n) time.

Processing events.

V-critical events.

Let v denote the vertex that induces a V-critical event. As the sweep plane reaches v, all edges incident to v start or cease to be swept; we call the former starting edges and the latter terminating edges. Let Q denote the polytope to which v belongs and let Π t 0 be the sweep plane containing v. When processing a V-event, we perform the following operations.

Create and delete combinatorial bitangents. Suppose first that the critical plane through v properly intersects Q. Consider in turn each combinatorial bitangent supported by a terminating edge, e t , incident to v and let h denote the other support edge of this bitangent. We check all starting edges incident to v to find the edge e s such that the line in Π t 0 +ε through e s and h is tangent to Q for ε > 0 arbitrarily small. We create a new combinatorial bitangent and delete the old one; in fact, we simply replace e t by e s in the combinatorial bitangent, create a pointer from edge e s to the bitangent, and update the event queue. After handling the last bitangent supported by edge e t , delete all the pointers from e t to the bitangents.

The critical plane through v contains O(k) bitangents through v, thus, by continuity, at most O(k) combinatorial bitangents are deleted and created. Each deletion and creation takes linear time in the degree of v plus O(k log n) time for updating the event queue (Lemma 5.2). Hence, since the sum of the degrees of the vertices is O(n), this step takes O(nk 2 log n) time in total for all non-extremal V-events.

Suppose now that the critical plane through v is tangent to Q and that all edges incident to v are starting. For each edge not incident to v, we can decide in constant time whether it supports a bitangent through v in the critical plane through v. Finally, if all edges incident to v are terminating, we delete all the O(k) bitangents supported by these edges; for each bitangent, deleting its blockers and the pointer from the edge not incident to v can be done in O(k) time. Hence, this takes O(k 2 ) time per critical event and O(k 3 ) time per sweep.

Update the combinatorial polygon associated with Q. This takes O(log n) time per polytope edge incident to v, thus O(n log n) time in total for all V-events.

Hence, processing all V-events takes O(nk 2 log n) time per sweep.

F-critical events.

We process an F-critical event as follows. Let b and f denote the bitangent and face associated with the event. Let e 1 and e 2 denote the two support edges of b such that e 1 is the edge that belong to f (see . By construction of F-events (see Section 5.4), e 2 does not intersect face f (see Figure 5.1c), thus the bitangent b is deleted and a new combinatorial bitangent is created.

Bitangent b is removed from the lists of bitangents supported by e 1 and e 2 in O(k) time. The support edges of the new bitangent are e 2 and the edge e 1 = e 1 of f that is intersected by the line in the plane Ψ (containing f ) through l e and e 2 (see Figure 5.1c). This edge e 1 is also one of the two edges adjacent to e 1 in its combinatorial polygon. Edge e 1 can thus be computed in O(log n) time. As usual, the new bitangent is added to the lists of bitangents supported by e 1 and e 2 . We then compute all the blockers of this new bitangent by performing one ray-shooting query per combinatorial polygon, for a total time of O(k log n). We finally update the event queue in O(k log n) time (Lemma 5.2).

There are O(k) F-events associated to each polytope face, thus O(nk) F-events per sweep. Hence, the total time complexity for processing all F-events is O(nk 2 log n) per sweep.

I-critical events.

An I-event is associated with a face f of some polytope P and an edge e 1 of some other polytope Q. Let p denote the point of intersection between f and e 1 . The sweep plane, Π t 0 , that contains p intersects the two polytopes P and Q in two polygons P t 0 and Q t 0 . See Figure 5.2. Point p lies on an edge of P t 0 ; the two endpoints of this edge are the intersection of two edges of P, say e 0 and e 2 . These two polytope edges can be computed in O(log n) time using the combinatorial polygon associated with P.

Create or delete combinatorial bitangents. If the two polygons P t 0 and Q t 0 are tangent at p (see Figure 5.2a), the two combinatorial bitangents whose pairs of support edges are (e 0 , e 1 ) and (e 1 , e 2 ) are either created or deleted at the I-event. If these bitangents appear in the list of bitangents having edge e 1 as support, we remove them from the list and delete them; this can be done brute force in O(k) time. Otherwise we create these two combinatorial bitangents. We compute their set of occluders in O(k log n) time by intersecting the bitangents with all the polytopes using their associated combinatorial polygons. Finally, we update the event queue in O(k log n) time.

Update sets of blockers. Consider now each of the O(k) bitangents having e 1 as a support edge except for the two bitangents that might have just been created. We update its set of blockers as follows. First, note that only polytope P may have to be added to, or removed from, the set of blockers. Two situations occur: either the geometric bitangent segment joining the two support edges in Π t 0 properly intersects polygon P t 0 , or not. In the first case (e.g., segment pq in Figure 5.2), polytope P was and remains a blocker of the bitangent. In the second case (e.g., segment pr in Figure 5.2), P has to be either removed from, or added to, the set of blockers. This can be done in O(k log k) time by searching for P in the set (recall that polytopes are ordered by their index in a binary search tree).

Processing an I-event thus takes O(k log n) time. Since any polytope edge intersects any other polytope in at most two points, there are O(nk) I-events which can be processed in O(nk 2 log n) time in total per sweep.

T-critical events.

Suppose that on the line transversal to e 1 , e 2 , e 3 and l e (the one associated to the T-event) edges e 1 , e 2 , e 3 are met in that order at points p 1 , p 2 , p 3 . Let Q i be the polytope containing e i , 1 i 3.

Update sets of blockers. Update the occluder set for the bitangent with support edges e 1 and e 3 by either removing Q 2 (if it appears in the set) or adding Q 2 (if it does not appear in the set); this can be done in O(log n) time.

Output. First determine if the segment p 1 p 3 is unoccluded by checking if the set of blockers of the bitangent with support edges e 1 and e 3 is empty or reduced to Q 2 . If so and if the segment intersects the reference edge e, then it is a free segment transversal to the four edges e, e 1 , e 2 , e 3 . In order to report each such transversal exactly once, we report it only if the reference edge e is smaller than e 2 for some global ordering of all edges. This can be done in constant time.

There are O(nk 2 ) T-critical events per sweep (see the proof of Proposition 3.3), thus all the T-events can be processed in O(nk 2 log n) time per sweep.

Complexity.

Note first that we assume a model of computation in which bounded-degree algebraic polynomials may be evaluated in constant time. See [START_REF] Everett | Predicates for line transversals in 3D[END_REF] for a detailed description of the predicates concerning line transversals that are used in this algorithm.

In this model of computation, we have described a Θ(n 2 k 2 log n)-time algorithm for computing all the minimal sets of edges, no two chosen from the same polytope, that admit an isolated line transversal containing a free segment that is tangent to all these polytopes. As mentioned earlier, the sweep-plane algorithm can be easily modified to report all types of minimal support sets.

The space used by the algorithm is Θ(nk 2 ) in the worst case. To see this, first notice that storing the combinatorial polygons and the V-, F-and I-critical events uses O(nk) space.

There are also O(nk) combinatorial bitangents in any sweep plane. Storing the combinatorial bitangents thus requires Θ(nk 2 ) space since, in the worst case, Θ(nk) of them may be intersected by Θ(k) polytopes. Furthermore, there may be Θ(nk 2 ) T-events in the queue since each of the Θ(nk) bitangents may share a support with Θ(k) other bitangents. This yields the bounds of Theorem 1.4 for computing minimal free segments.

Notice that, with a slight modification to the algorithm, and no increase in the time complexity, we can reduce the storage requirement of the T-events to O(nk). To do this we maintain the bitangents sorted by polar angle around each vertex of the combinatorial polygons, which can easily be done since the cyclic ordering changes only at T-critical events or when a bitangent is created or deleted. Since two bitangents become aligned only when they are neighbors in this cyclic ordering, we only need to maintain the T-events for pairs of consecutive bitangents and there can only be O(nk) of these at any one time.

Finally, the bounds of Theorem 1.4 that concern the computation of potentially occluded isolated lines tangent to polytopes are obtained by noticing that we need not maintain the sets of blockers of the bitangents which reduces the space requirements for the combinatorial bitangents to O(nk).

Conclusion.

We have presented a tight bound on the number of (connected components of) lines and maximal free line segments that are tangent to at least four among k possibly intersecting polytopes in arbitrary position. A problem that we leave open is to prove that the same bound holds for the combinatorial complexity of the set of all maximal free line segments among k polytopes.

We have also shown how to compute in near-optimal worst-case time all the minimal free line segments that are isolated transversals to their set of supports and tangent to the corresponding polytopes. We believe that our algorithm can also be made to report all connected sets of minimal free segments that are transversal to the same set of edges. A problem that we have not solved, however, is to compute in the same time and space complexities, respectively, the polytopes supporting the endpoints of the corresponding maximal free line segments.

  ure 2.7(a)), or m properly intersects Q ∩ Ψ which is then a face or an edge of Q (see Figure 2.7(b))

FIG. 2 . 7 .

 27 FIG. 2.7. m is tangent to P along a face in Ψ and (a) to Q ∩ Ψ only on l e or (b) to Q along a face in Ψ.

2 A 1 FIG. 4 . 1 .

 2141 FIG. 4.1. Lower bound examples for Lemmas 4.1 and 4.2.

FIG. 5 . 1 .

 51 FIG. 5.1. (a) The sweep plane in which the combinatorial bitangent with support edges e 1 and e 2 is created. (b) The sweep plane at a T-critical event induced by the three bitangents with support edges in e 1 , e 2 , and e 3 . (c-d) A line that defines an F-critical event. (d) The F-event defined by occurs simultaneously with an I-critical event.

FIG. 5 . 2 .

 52 FIG. 5.2. I-critical event.

  FIG. 2.1. Plane Π t contains edge e and intersects polytopes P, Q, and R in polygons P t , Q t , and R t .

	Π t	Q	R
	l e
	P	Q t	R t
	e	P t

  Lines through x in Π t and tangent to P t and Q t .

	e	x	e	x
	Q t	P t		P t
	Π t	Π t		Q t
	(a)			(b)
	FIG. 2.5.

  intersects its supports in at least two distinct points. Moreover the set of supports of m t * is u. Thus there is a unique line in Π t * whose set of supports contains u. Hence u is a maximal(P t * , Q t * )-tuple. By Lemma 2.8, m t is the unique line in Π t whose set of supports contains u for all t = t * in N . Thus u is a maximal (P t , Q t )-tuple for all t = t * in N . Hence u is a maximal (P t , Q t )-tuple for all t ∈ N , contradicting the hypotheses of Lemma 2.3 We first prove that the supports in u are supports of m t for all t ∈ N A support vertex in u lies on l e by Lemma 2.8 and thus lies in Π t for all t. A support vertex in u also

	and thus concluding the proof of Lemma 2.12.
	LEMMA 2.13. The set of supports of m t is u for some t in any sufficiently small open neighborhood N of t * .
	Proof.

and 2.14 imply that the set of supports of m t is invariant and equal to u for all t in any sufficiently small open neighborhood N of t * . Moreover, since m t varies continuously with t and m = m t * is tangent to P t * and Q t * (by Lemma 2.10), line m t is tangent to P t and Q t for all t ∈ N . Hence u is a (P t , Q t )-tuple for all t ∈ N . We now prove that u is a maximal (P t , Q t )-tuple for all t ∈ N .

As we have seen before, m = m t * is tangent to P in at least two points (by Lemma 2.10), thus m t *

  If so, we check, for each edge incident to v, if the line in plane Π t 0 +ε that goes through these two edges is tangent to Q for ε > 0 arbitrarily small. If so, we create a new combinatorial bitangent. By continuity, O(k) bitangents are created in total time O(n + kd) where d is the degree of v. For each of these newly created bitangents, we compute its set of blockers in (brute force) O(n) time and update the event queue in O(k log n) time (Lemma 5.2). This takes O(nk log n) time per event, hence O(nk 2 log n) time per sweep since there are at most two sweep planes tangent to any polytope.

The set of polytopes to which the line is tangent might change during the motion.

When the polytopes are fully dimensional, a segment is free if it does not intersect the interior of any of them. Our definition ensures that a segment is free also when it intersects and is coplanar with a two-dimensional polytope. The endpoints of a free segment may also lie on the boundary of a polytope.

Such an interval could be open or closed, a single point or an interval of positive length.

Note that in these two situations, two edges of two distinct polytopes are then coplanar (in the first case an edge of Q and e are coplanar, and in the later case a face of P is coplanar with a face or an edge of Q). Hence proving this lemma is straightforward under some general position assumption that excludes such situations.

This research was supported by the McGill-ISA collaborative INRIA project, NSERC, FCAR and NSF.