Olivier Devillers
email: olivier.devillers@inria.fr

Hazel Everett

Sylvain Lazard

Maria Pentcheva

Stephen Wismath
email: wismath@cs.uleth.ca

Drawing K n in Three Dimensions with One Bend per Edge

We give a drawing of Kn in three dimensions in which vertices are placed at integer grid points and edges are drawn crossing-free with at most one bend per edge in a volume bounded by O(n 2.5 ).

Introduction

Drawing graphs in three dimensions has been considered by several authors in the graph-drawing field under a variety of models. One natural model is to draw vertices at integer-valued grid points in a 3D Cartesian coordinate system and represent edges as straight line segments between adjacent vertices with no pair of edges intersecting. The volume of such a drawing is typically defined in terms of a smallest bounding box containing the drawing and with sides orthogonal to one of the coordinate axes. If such a box B has width w, length l and height h, then we refer to the dimensions of B as (w + 1) × (l + 1) × (h + 1) and define the volume of B as (w + 1) • (l + 1) • (h + 1). Note that the volume of B then exactly measures the number of grid points in (or on) the box B.

It was shown by Cohen, Eades, Lin and Ruskey [START_REF] Cohen | Three-dimensional graph drawing[END_REF] that it is possible to draw any graph in this model, and indeed the complete graph K n is drawable within a bounding box of volume Θ(n 3 ). A lower bound of Ω(n 3 ) on the volume of any such drawing of K n is easily seen via a sweeping plane argument. An axis-parallel plane cannot contain 5 vertices as an edge crossing would then be necessarily produced. Thus, the size of each dimension is n/4 or greater.

Restricted classes of graphs may however be drawn in smaller asymptotic volume. For example, Calamonieri and Sterbini [START_REF] Calamoneri | 3D straight-line grid drawing of 4-colorable graphs[END_REF] showed that 2-, 3-, and 4-colourable graphs can be drawn in O(n 2 ) volume. Pach, Thiele and Tóth [START_REF] Pach | Three-dimensional grid drawings of graphs[END_REF] showed a volume bound of Θ(n 2 ) for r-colourable graphs (r a constant). Dujmović, Morin and Wood [START_REF] Dujmović | Layout of graphs with bounded tree-width[END_REF] investigated the connection of bounded treewidth to 3D layouts. Felsner, Liotta and Wismath [START_REF] Felsner | Straight-line drawings on restricted integer grids in two and three dimensions[END_REF] showed that outerplanar graphs can be drawn in O(n) volume. Establishing tight volume bounds for planar graphs remains an open problem. Dujmović and Wood [START_REF] Dujmović | Three-dimensional grid drawings with subquadratic volume[END_REF] showed an upper bound of O(n 1.5 ) on the volume of planar graphs at Graph Drawing 2003.

In 2-dimensional graph drawing, the effect of allowing bends in edges has been well studied. For example, Kaufmann and Wiese [START_REF] Kaufmann | Embedding vertices at points: few bends suffice for planar graphs[END_REF] showed that all planar graphs can be drawn with only 2 bends per edge and all vertices located on a straight line.

The consequences of allowing bends in 3 dimensions has received little attention. Note that bend points must also occur at integer grid points. Bose, Czyzowicz, Morin, and Wood [START_REF] Bose | The maximum number of edges in a three-dimensional grid-drawing[END_REF] showed that the number of edges in a graph provides an asymptotic lower bound on the volume regardless of the number of bends permitted, thus establishing Ω(n 2 ) as the lower bound on the volume for K n . This lower bound was explicitly achieved by Dyck, Joevenazzo, Nickle, Wilsdon and Wismath [START_REF] Dyck | Drawing K n in Three Dimensions with Two Bends Per Edge[END_REF] who presented a construction with at most 2 bends per edge. The upper bound is also a consequence of a more general result of Dujmović and Wood [START_REF] Dujmović | Stacks, queues and tracks: Layouts of graph subdivisions[END_REF]. In [START_REF] Morin | Three-dimensional 1-bend graph drawings[END_REF], Morin and Wood presented a one-bend drawing of K n that achieves O(n 3 / log 2 n) volume. It is the gap between this result and the Ω(n 2 ) lower bound that motivates this paper; we improve the Morin and Wood result to achieve a one-bend non-crossing drawing with volume O(n 2.5 ).

We call the axes of our 3D Cartesian coordinate system respectively X, Y and Z.

The one-bend construction of K n by Morin and Wood [START_REF] Morin | Three-dimensional 1-bend graph drawings[END_REF] considers O(log n) packets of O( n log n ) collinear vertices. All the vertices lie in the XY -plane and edges joining vertices of different packets lie above this plane. Edges joining vertices within a packet lie below this plane and the volume of these (complete) subgraphs is a consequence of the following lemma. Lemma 1 ( [START_REF] Morin | Three-dimensional 1-bend graph drawings[END_REF]) For all q 1, K m has a one-bend non-crossing drawing in an axis-parallel box of size q × m × π 2 3 m 2 q with all the vertices on the Y -axis.

Indeed, Ω(n 3 ) volume is required for a collinear one-bend drawing of K n as shown by Morin and Wood. We present here a brief description of the construction behind Lemma 1 because we will use it in our construction. The edges are divided into Θ(m 2 ) chains of edges (i.e., sequences of edges). A chain connects all vertices with index equal to i modulo j such that the vertices on the chain are ordered with increasing indices. In each chain, the bends are placed on a line parallel to the Y -axis through a point of integer coordinates (x, z) in the XZ-plane. The chains thus lie in planes that contain the Y -axis (where the vertices lie). In the XZ-plane, the points (x, z) are chosen so that they are all strictly visible from the origin. The well-known fact that there are Θ(m 2 ) such choices in a rectangle of size q × m 2 q ensures that all the Θ(m 2 ) chains can be placed in distinct planes, and thus in a way that the edges do not cross.

The construction

Recall that the problem we solve is to draw a complete graph on a threedimensional integer-valued grid where the edges do not cross, and they have at most one bend. Both the vertices and the bends are placed at nodes of the grid. The goal is to minimize the volume of the bounding box of this drawing. In this section, we present our construction.

The construction is roughly as follows (see Figures 1 and2). We split the n vertices into k packets of n k vertices, where all vertices in one packet have the same X and Z coordinates. All edges of the complete graph contain a bend. All edges joining two vertices of one packet are placed below and right (positive X direction) of the packet, and all edges joining two vertices of different packets are placed "above". We present our construction for an arbitrary k and show later that the volume of the bounding box of the drawing is minimized for k = n 1 4 . We assume for simplicity that n k is an integer.

X and Y coordinates of the vertices. We first describe the X and Ycoordinates of the vertices. Refer to Figure 1(a). All vertices have different Y-coordinates, ranging between 0 and n -1. We divide the set of n vertices into k packets, denoted V 0 , . . . , V k-1 , of n k vertices. All vertices in the same packet V i have the same X-coordinate 2i, the same Z-coordinate z i (which we will define later), and consecutive Y-coordinates. Precisely, the j-th vertex in the i-th packet, denoted v i,j , has coordinates (2i, i n k + j, z i ), with 0

¡ k 2( -1) n k ¢ £ n k k -1) 2( ¤ ¥¦ §¦ ¨© §© § Z X Y k 0 § § § 2 Z Y X 0 4
j n k -1 and 0 i k -1.
Edges joining vertices of one packet. Refer to Figure 1(b). Since all the vertices of one packet are collinear, we can draw the complete graph on these vertices using the q × m × O(m 2 /q) volume construction of Morin and Wood [START_REF] Morin | Three-dimensional 1-bend graph drawings[END_REF] described in Section 2. In that construction there are m collinear vertices; here we have m = n k vertices. We choose q = k and draw the edges such that the bounding box of this complete subgraph is below (negative Z) and to the right (positive X) of the vertices. Notice that we have chosen q = k so that these complete subgraphs do not asymptotically increase the width of the final drawing.

In the sequel of the construction, we only consider edges that join vertices of distinct packets, and their bends.

X and Y coordinates of the bends. Recall that v i,j denotes the j-th vertex of the i-th packet. The bend of an edge joining vertex v i1 ,j1 to vertex v i2,j2 , with i 1 < i 2 , is denoted e i1,j1→i2,j2 . It separates the edge into two distinct segments, the outgoing segment which starts at v i1,j1 and ends at e i1,j1→i2,j2 , and the incoming segment which starts with e i1,j1→i2 ,j2 and ends at v i2 ,j2 .

Refer to Figure 2. A bend e i1,j1→i2,j2 has coordinates (2i

2 -1, i 1 n k +j 1 , z i2,j2
), that is, its X-coordinate is one less than the X-coordinate of v i2,j2 , its Ycoordinate is the same as for v i1 ,j1 , and its Z-coordinate, which only depends on v i2,j2 , will be defined later. (Notice that the bends of all edges ending at the same vertex have the same Z-coordinate).

Y -1) k 2( -1) k ¡ ¡ ¢ ¢ £ £ ¤ ¤ ¥ ¥ ¦ ¦ § § ¨© © 0 2 1 Z Y X 0 X Z 2 2(
Z-coordinates of the vertices and bends. We assign values to z i and z i,j so that edges do not cross. In fact, our construction is designed to verify the following lemma. In the following, we consider the projection on the XZ-plane of the vertices v i, and bends e , →i,j where can take any value. Note that the projections of v i, and e , →i,j are independent of the choice of . Refer to Figures 2 and3(a).

Lemma 2 Consider the projection of the drawing onto the XZ-plane. Then, the polar ordering ≺ i0 about v i0, of all vertices v i, and bends e , →i,j such that i 0 < i < k and 0

j < n k satisfies v i-1, ≺ i0 e , →i,0 ≺ i0 . . . ≺ i0 e , →i,j ≺ i0 . . . ≺ i0 e , →i, n k -1 i0 v i, .
Before proving Lemma 2, we describe our construction. The general idea is that, in projection onto the XZ-plane, all bends e , →i, should lie above the line joining v i-2, to v i-1, , and below the line joining v i-1, to v i, (see Figure 3(a)). Hence, if s i-1 and s i denote the slopes of these two lines, they should obey the recurrence s i = s i-1 + n k + 1. More precisely, the construction goes as follows.

First, let z 0 = 0 and z 1,j = j + 1, then z 1 is chosen such that v 1, is at the same polar angle about v 0, as e 0, →1, n k -1 , which gives z 1 = 2z 1, n k -1 = 2 n k . Assume now that we have placed vertices and bends up to index i. To get a correct polar ordering around v i-1, we need to have the next bends above the line through v i-1, and v i, thus we place the next bend at z i+1,0 = z i + 1 2 (z i -z i-1 ) + 1 and the following bends on edges going to v i+1, at z i+1,j = z i + 1 2 (z i -z i-1 ) + 1 + j. The next vertex v i+1, is placed at the same polar angle about v i, as e , →i+1, n k -1 which gives

X Z v i 0 , v i,
z i+1 = z i + 2(z i+1, n k -1 -z i ) = z i + 2( zi-zi-1 2 + n k ) = 2z i -z i-1 + 2 n k ; solving this recurrence 1 yields z i = i(i + 1) n k . Then we obtain z i,j = z i-1 + 1 2 (z i-1 -z i-2 ) + 1 + j = (i -1)(i + 1) n k + 1 + j.
To summarize, the coordinates of the vertices and bends are

v i,j = 2i, i n k + j, i(i + 1) n k e i1,j1→i2,j2 = 2i 2 -1, i 1 n k + j 1 , (i 2 2 -1) n k + 1 + j 2
Proof of Lemma 2: The correct polar ordering of the v i, viewed from v i0 , is guaranteed since all these points are ordered on a convex curve (i.e. a parabola). Let L i be the line through v i, and v i+1, . The correct polar ordering of v i, , the e , →i+1,j and v i+1, , viewed from v i, , comes directly from the construction; moreover, this ordering is the same for all viewpoints v i0, , i 0 < i, since these viewpoints lie above L i-1 (see Figure 3(a)). 2

Proof of correctness

We say that two edges cross if their relative interiors intersect. We prove in this section that no two edges of our construction cross. We first show that an edge joining two vertices within the same packet crosses no other edge in the drawing. Then, we show that there is no crossing between two outgoing segments, two incoming segments, and finally one outgoing and one incoming segment.

1 An inductive verification is easy since with this formula we have:

2z i -z i-1 + 2 n k = n k [2i(i + 1) -i(i -1) + 2] = n k [i 2 + 3i + 2] = (i + 1)(i + 2) n k = z i+1 .
Edges joining vertices within packets. Two edges joining vertices within a given packet do not cross by Lemma 1 (proved in [START_REF] Morin | Three-dimensional 1-bend graph drawings[END_REF]). An edge joining vertices within a packet crosses no other edge joining vertices within another packet since the projection onto the Y -axis of the bounding boxes of the Morin-Wood constructions do not intersect. Finally, the bounding box of the Morin-Wood construction properly intersects no edge joining distinct packets since they do not properly intersect in XZ-projection (see Figure 3(b)). Hence, the edges joining vertices within a packet cross no other edge.

Outgoing-outgoing segments. Refer to Figure 2(a). If two outgoing segments start from different vertices, they lie in two different planes parallel to the XZ-plane. Otherwise, by Lemma 2, the two segments only share their starting point. Hence no two outgoing segments cross.

Incoming-incoming segments. Refer to Figure 2(b). We first remark that an incoming segment joining e , →i,j to v i,j lies in the plane P i,j through the two lines parallel to the Y -axis and containing, respectively, all the e , →i,j and all the v i, .

For a pair of incoming segments, we consider three cases according to whether both segments finish at the same vertex, at distinct vertices of the same packet, or at vertices of different packets. In the first case, the segments live in a plane P i,j ; they start at different bends and end at the same vertex, hence they do not cross. In the second case, the two segments live in two planes P i,j and P i,j whose intersection is the line v i,j v i,j . The segments end there and thus cannot cross. In the third case, the segments do not overlap in the X-direction, thus they do not cross.

Incoming-outgoing segments. Consider an outgoing segment joining vertex v i1, to bend e i1, →i3, and an incoming segment joining bend e , →i2, to vertex v i2, , where can be any value (see Figure 4). The ranges over the X-axis of the two segments are [2i 1 , 2i 3 -1] and [2i 2 -1, 2i 2 ]. They overlap only if i 1 < i 2 < i 3 , and, in such a case, Lemma 2 yields that, viewed from v i1, , the points satisfy the polar ordering e , →i2, i1 v i2 , ≺ i1 e i1, →i3, . This implies that, in projection onto the XZ-plane, points e , →i2, and v i2, are below the line segment joining v i1, and e i1, →i3, (see Figure 4). Hence the two segments do not cross.

Volume analysis

The dimension of the bounding box of our construction for edges between packets has size smaller than 2k × n × kn since the highest vertex has Z- . Recall that we assumed for simplicity that k and n k were integers; for any n we can apply our construction with n

coordinate z k-1 = k(k -1) n k .

Conclusion

We have presented a construction of volume O(n 2.5 ) for a one-bend drawing of the complete graph K n by a hierarchical organisation of the graph where edges inside packets are drawn with the cubic result of Pat Morin and David Wood for collinear vertices. By arranging the packets of points on different planes, the remaining edges can be drawn more compactly.

While our result is a significant improvement over previous constructions, it remains to close the gap between our O(n 2.5 ) upper bound and the Ω(n 2 ) lower bound. Another open problem is to minimize the bounding box aspect ratio of the drawing without increasing its volume.

Figure 1 :

 1 Figure 1: (a) k packets of n k vertices; (b) bounding boxes of the complete graphs of packets of vertices. Here, n = 16 and k = 4.

Figure 2 :

 2 Figure 2: (a) all edges starting from one vertex; (b) all edges ending at one vertex. Here, n = 16 and k = 4.

Figure 3 :

 3 Figure 3: (a) Construction of the Z-coordinates of the vertices (dots) and bends (squares); (b) XZ-projection of the bounding boxes of the interpacket edges.

Figure 4 :

 4 Figure 4: Incoming and outgoing segments in XY and XZ-projections.

1 4 4 Theorem 3 4 ) 4 )

 14344 vertices and then remove the extra vertices and edges. We thus have the following result. Every complete graph K n has a one-bend non-crossing drawing in an axis-parallel box of dimensions O(n 1 × n × O(n 5 and volume O(n 2.5 ).

Acknowledgments

We thank Sebastian Hanlon and Carrie Wang for software implementations related to this work, and Ethan Kim and Jeff Erickson for discussions related to this result.

A preliminary version of this work was presented at Graph Drawing 2005. Research supported in part by NSERC Canada.


H Br Önnimann

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

V Dujmović

H Everett

M Glisse

X Goaoc

S Lazard

H.-S Na

S Whitesides

The Number of Lines Tangent to Arbitrary Convex Polyhedra in 3D

Keywords: F.2.2 [Nonnumerical Algorithms and Problems]: Geometrical problems and computations, G.2.1 [Combinatorics]: Counting problems, I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling, I.3.7 [Three-Dimensional Graphics and Realism]: Visible line/surface algorithms Algorithms, Theory Computational geometry, 3D visibility, visual events, visibility complex Qt+ Pt+ Pt-Pt Qt

We prove that the lines tangent to four possibly intersecting convex polyhedra in 3 with n edges in total form Θ(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 arbitrary degenerate scenes. More generally, we show that a set of k convex polyhedra with a total of n edges admits, in the worst case, Θ(n 2 k 2 ) connected components of (possibly occluded) lines tangent to any four of these polyhedra. We also show a lower bound of Ω(n 2 k 2 ) on the number of non-occluded maximal line segments tangent to any four of these k convex polyhedra.

INTRODUCTION

Computing visibility relations in a 3D environment is a central problem of computer graphics (e.g. determining the view from a given point, identifying the set of blockers between two polygons, computing the umbra and penumbra cast by an area light source) and other engineering tasks (e.g. radio propagation simulation). Visibility is well-known to account for a significant portion of the cost of the overall computation in these applications, and 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, including space partitions, aspect graphs, and visual hulls).

One such structure, the visibility complex [START_REF] Pocchiola | The visibility complex[END_REF], which has been proposed for rendering [START_REF] Durand | The 3D visibility complex[END_REF], encodes visibility relations by partitioning the set of maximal free line segments. Unfortunately the complex is potentially enormous which has so far prevented its application in practice. Its size is intimately related to the number of lines tangent to four objects in the scene; for n triangles in 3 , the complex can have size Θ(n 4 ) in the worst case [START_REF] Durand | 3D Visibility: Analytical study and Applications[END_REF], even when the triangles form a terrain (see Figure 1).

There is evidence, both theoretical [START_REF] Devillers | The expected number of 3D visibility events is linear[END_REF] and practical [START_REF] Durand | The visibility skeleton: a powerful and efficient multi-purpose global visibility tool[END_REF], that this bound is largely pessimistic in practical situations. The lower bound examples are carefully manufactured to exhibit the worst-case behavior, and often require an unrealistically large ratio between longest and shortest edges. On the other hand, 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 it is at most quadratic.

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. If a scene consists of k disjoint convex polyhedra with n edges in total then, under a strong general position assumption, the number of tangents to four of the polyhedra is at most O(n 2 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 sil-houette 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].

Our results. In this paper, 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 (i.e., convex polyhedra) 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 [START_REF] Brönnimann | On the Number of Lines Tangent to Four Convex Polyhedra[END_REF]. 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.

Secondly we consider polytopes in arbitrary position: we drop all general position assumptions. Four such objects may admit an infinite number of common tangents which can be partitioned in line space into connected components. Two lines are said to be in the same connected component if and only if their corresponding points in line space (e.g., Plücker space) are in the same connected component of the set of points corresponding to all the lines tangent to any 4 among the k objects; equivalently one line can be continuously moved into the other while remaining tangent to at least four objects 1 .

Our main results are the following.

Theorem 1. Given 4 polytopes in 3 with n edges in total, the number of lines tangent to the 4 polytopes is, in the worst case, either infinite or Θ(n 2 ). More generally, these lines form Θ(n 2 ) connected components. Moreover, if one of the polytopes has m edges, these bounds improve to Θ(mn). This result improves 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) of total complexity O(n) [START_REF] Agarwal | On stabbing lines for convex polyhedra in 3[END_REF].

Theorem 2. Given k polytopes in 3 with n edges in total, the lines (possibly occluded) tangent to any four of the polytopes form, in the worst case, Θ(n 2 k 2 ) connected components.

This result improves the trivial bound of O(n 4 ). Our results hold for any set of polytopes including those that degenerate to a polygon, segment or point 2 . The polytopes may intersect in any way; they may overlap or coincide and their faces may be triangulated.

To emphasize the importance of considering intersecting polytopes, observe that computer graphics scenes usually consist of not necessarily convex objects which can, however, 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 yield new tangents which 1 Notice that the set of objects the line is tangent to might change during the motion. 2 A line is tangent to a polytope with non-empty interior if and only if it intersects the polytope but not its interior. We also use this definition if the polytope is a segment or a point; if the polytope is a polygon then a line is a tangent line if and only if it intersects the 2D boundary of the polygon. were not present in the original scene; indeed a line tangent to two polytopes along a shared face is not tangent to their union.

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. Note that we could not find a perturbation argument that guarantees the preservation of all connected components of tangents and we do not believe it is a simple matter.

The paper is organized as follows. We prove the upper bounds of Theorems 1 and 2 in Sections 2 and 3, and the lower bounds in Section 4.

MAIN LEMMA

We prove in this section the following lemma which yields the upper bounds in Theorem 1. This lemma is also fundamental for the proof of the upper bound of Theorem 2, which we provide in Section 3.

Consider three polytopes P, Q, and R in 3 , with p, q, and r edges, respectively, and let e be an edge of a fourth polytope S.

Main Lemma. The lines intersecting e and tangent to P, Q, R and S form O(p + q + r) connected components.

The upper bounds of Theorem 1 follow from the Main Lemma. Indeed, if s denotes the number of edges of S, by summing over all these edges, the number of connected components of lines tangent to the four polytopes is O(s(p+ q + r)) = O(n 2 ). Moreover, if one of the polytopes has m edges, choosing S to be this polytope yields that the lines tangent to the four polytopes form O(mn) connected components.

The actual proof of the Main Lemma is rather complicated because it handles polytopes which may intersect in any way. In addition, the proof handles all the degenerate cases. To assist the reader, we first give an overview of the proof.

Proof overview

The proof is inspired by a method which was, to our knowledge, first used in [START_REF] Berg | Sparse arrangements and the number of views of polyhedral scenes[END_REF] (see also Schiffenbauer's survey [START_REF] Schiffenbauer | A Survey of Aspect Graphs[END_REF]).

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 Pt, Qt, and Rt, respectively (see Figure 2).

During the sweep, we track the bitangents, that are the lines tangent to Pt and Qt, or to Qt and Rt. As the sweep plane rotates, the three polygons deform and the bitangents move accordingly. Every time two bitangents become aligned during the sweep, their supporting line is tangent to P, Q, and R. A bitangent to two polygons, say Pt and Qt, goes through a set of vertices of these polygons. The edges of P and Q that contain these vertices are called support edges of the bitangent. (For the purpose of this overview we ignore the case where bitangents go through vertices of P or Q).

In any given instance of the sweep plane Πt, we consider the pairs of bitangents (one involving Pt and Qt, and the other Qt and Rt) that share a vertex of Qt (see Figure 2). The sets of edges that consist of e and the support edges of two such bitangents are called candidate tuples. A candidate tuple contains at least 4 edges, e and at least one edge from each polytope; most of the time, it contains exactly 4 edges.

A candidate tuple induced by an instance of the sweep plane changes as the plane rotates only when a support edge of a bitangent changes. We define critical planes in such a way that the support edges of the bitangents do not change as the sweep plane rotates in between two consecutive critical planes. As the sweep plane rotates, the support edges of a bitangent change if a support edge starts or ceases to be swept, or if, during its motion, the bitangent becomes tangent to one of the polygons along an edge (see Figure 3). We thus define two types of critical planes. An instance of the sweep plane is called V-critical if it contains a vertex of one of the polytopes, and F-critical 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 3 and4). We will show that the number of critical planes is O(p + q + r).

Notice that 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. 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 total number of distinct candidate tuples. In the detailed proof of the lemma (Section 2.2), 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 connected components of lines intersecting e and tangent to P, Q, and R.

Proof of the Main Lemma

We now give a detailed proof of the Main Lemma for the general case of possibly intersecting polytopes in any configuration.

Since any line tangent to a polytope will remain tangent whether or not the faces are triangulated (or otherwise subdivided), we assume without loss of generality that no two faces of P are coplanar, and similarly for Q, R and S.

We can also assume without loss of generality that P, Q, R and S have non-empty interior. Indeed, if some polytopes have empty interior, they can be "inflated" as follows so that there are not more connected components of lines tangent to the four polytopes before the inflation than after3 . If, say, P is a segment (resp. a point) it can be first transformed into any triangle having this segment (resp. point) as an edge (resp. vertex) without losing any common tangent line to the four polytopes. Now, if P is a polygon it can be "inflated" by adding a vertex that projects orthogonally onto P. Let P and P be two inflated instances of P for which the added vertices are added on opposite sides of P respectively. Then any line tangent to P is tangent to P or P .

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

A line intersecting e and tangent to P, Q, R and S is called a generic tangent line if it is tangent to Pt, Qt, and Rt in some plane Πt. Otherwise it is called a nongeneric tangent line. A nongeneric tangent line properly 4 intersects Pt, Qt, or Rt in some plane Πt. In this case Pt, Qt, or Rt is a face or an edge of P, Q, or R lying in Πt, a degenerate situation.

We bound in the two following subsections the number of generic and non-generic tangent lines.

Generic tangent lines

We start with some definitions. We call support vertex of a line, a vertex of P, Q, or R that lies on the line. We call support edge of a line, an edge of P, Q, or R that intersects the line and has no endpoint on it. A support is a support edge or support vertex.

For any t, a bitangent to polygons Pt and Qt is a line tangent to Pt and Qt in Πt (the line may intersect the polygon Rt in any way). For any t, let a (Pt, Qt)-tuple be the nonordered set of all supports in P and Q of one of the bitangents to polygons Pt and Qt. Note that a (Pt, Qt)-tuple consists of exactly one support in P and one support in Q except when the corresponding bitangent is tangent to P (or Q) along a face; then the (Pt, Qt)-tuple contains two supports in P (or Q) instead of one. A PQ-tuple is a set of edges and vertices that is a (Pt, Qt)-tuple for some t. We define similarly the (Qt, Rt)-tuples and QR-tuples. We say that a (Pt, Qt)-tuple is maximal for some t if it is not contained in any other (Pt, Qt)-tuple, for the same t. Note that a (Pt, Qt)-tuple is non-maximal for some t only if all its supports intersects Πt in one and the same point (see Figure 6(b)).

For any t, let a (Pt, Qt, Rt)-tuple be the union of a (Pt, Qt)tuple and a (Qt, Rt)-tuple that share at least a support in Q. A (Pt, Qt, Rt)-tuple is maximal for some t if it is not contained in any other (Pt, Qt, Rt)-tuple, for the same t. A PQR-tuple is a set of edges and vertices that is a (Pt, Qt, Rt)-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. Lemma 3. The set of supports of a generic tangent line is a PQR-tuple.

Proof. Any generic tangent line is tangent in Πt to Pt, Qt, and Rt for some value t. Thus the set of supports of in P and Q (resp. in Q and R) is a (Pt, Qt)-tuple (resp. a (Qt, Rt)-tuple). Moreover these (Pt, Qt)-tuple and (Qt, Rt)tuple contain the same supports in Q, thus their union is a (Pt, Qt, Rt)-tuple, hence a PQR-tuple.

We now define the critical planes Πt in such a way that the set of (Pt, Qt, Rt)-tuples is invariant for t ranging strictly in 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 5 on le. A plane Πt is F-critical relative to polytopes (P, Q) if (see Figure 4) it contains a line such that (i) lies 6 in a plane Ψ = Πt containing a face of P, and (ii) is tangent in Ψ to polygon 7 Q ∩ Ψ or P ∩ Ψ, at some point not on le. 5 This constraint ensures that the number of V-critical planes is finite even in degenerate configurations. 6 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. 7 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 le 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 le (see Figure 10 at the end of the paper).

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 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 couples (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 \ le. 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 4. There are at most 2 3 (p+q+r) V-critical events and 83 (p + 2 q + r) F-critical 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. Let be a line lying in some plane Πt and satisfying with plane Ψ Conditions (i-ii). Plane Ψ does not contain le because otherwise both le and lie in the two distinct planes Ψ and Πt, so = le but then cannot satisfy Condition (ii). Furthermore and le intersect or are parallel since they both lie in Πt. Thus if Ψ ∩ le is a point then contains it, and otherwise Ψ ∩ le = ∅ and is parallel to le.

There are at most four lines in plane Ψ going through Ψ ∩ le if this intersection is a point and parallel to le otherwise, and tangent to Q ∩ Ψ or P ∩ Ψ, at some point not on le. Moreover each such line is contained in a unique plane Πt, for t ∈ [0, π], since = le ( contains a point not on le). 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).

We now prove that the critical planes have the desired property. Let ue be the set of supports of le in P and Q. Lemma 5. If u = ue is a maximal 8 (Pt, Qt)-tuple for some but not all t in every open neighborhood of t * , then t * is a critical value.

Moreover, there exists a V-critical event (t * , v) or a Fcritical 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.

Proof. We can assume that there exists an open neighborhood N = (t0, t1) of t * such that u is a maximal (Pt, Qt)tuple for t = t * or all t ∈ (t * , t1) (or by symmetry for all t ∈ (t0, t * )), but is not a maximal (Pt, Qt)-tuple for all t ∈ N . Indeed, suppose that Lemma 5 is proved if u satisfies this additional assumption. If u does not satisfy this additional assumption, then there exists, in every open neighborhood of t * , infinitely many maximal intervals (open or closed and possibly of zero length) in which either u is a maximal (Pt, Qt)-tuple for all t or u is not a maximal (Pt, Qt)-tuple for all t. However, in this case, our assumption that Lemma 5 holds if u satisfies the above additional assumption yields that each endpoint of these intervals is a critical value, contradicting Lemma 4.

We can also assume that u contains no vertex v, or edge with endpoint v, such that v lies on Πt * \le 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 claims that yields the result. Indeed, we prove the existence of a line m in Πt * whose set of supports contains u (Claim C) such that (i) m lies in a plane Ψ = Πt * containing a face of P (Claim D), and (ii) m is tangent in Ψ to polygon Q ∩ Ψ or P ∩ Ψ, at some point not on le (Claim E). 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.

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

Claim A. Each support in u intersects Πt in exactly one point (possibly on le), 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 (Pt * , Qt * )-tuple.

Proof of Claim A. Since u is a (Pt, Qt)-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, or edge with endpoint v, such that v lies on Πt * \ le 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 le or intersects Πt in exactly one point for all t ∈ N . However, no edge of u lies in le because otherwise, if x denotes such an edge of, say, P, then any line tangent to Pt 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 (Pt, Qt)-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 (Pt, Qt)-tuple. Then polygons Pt and Qt are both reduced to point v because otherwise u is not maximal (indeed a line in Πt tangent to Pt and Qt at v can be rotated about v until it becomes tangent to Pt or Qt in some other points). Thus v is a vertex of P and of Q because the polytopes have non-empty interior. It follows that v is a support in u. Thus vertex v lies on le since each support in u intersects Πt for all t ∈ N . Moreover, since Pt and Qt are both reduced to point v, the set of supports of le is u, contradicting the hypotheses of Lemma 5.

Thus, if u is a maximal (Pt, Qt)-tuple for all t ∈ (t * , t1), the union of the supports in u intersects Πt in at least two distinct points for all t ∈ (t * , t1) and thus for all t = t * in any sufficiently small open neighborhood of t * . Also, if u is a maximal (Pt, Qt)-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 * . 2

Claim B. If u is a maximal (Pt * , Qt * )-tuple then u consists of at least three supports. Proof of Claim B. Suppose for a contradiction that u consists of only two supports. It follows from Claim A that 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 mt in Πt whose set of supports contains u; moreover mt is continuous in terms of t. Since u is a (Pt * , Qt * )-tuple, the set of supports of mt * is u. Thus, for all t in any sufficiently small N , the set of supports of mt is u. It follows, since mt * is tangent to Pt * and Qt * , that mt is tangent to Pt and Qt for all t ∈ N .

Π t * m = Π t * ∩ Ψ P t * le face of P in Ψ Q t *
Hence, for all t ∈ N , line mt, whose set of supports is u, is tangent to Pt and Qt in Πt. Thus u is a (Pt, Qt)-tuple for all t ∈ N . Moreover, mt is the unique line in Πt whose set of supports contains u, thus u is a maximal (Pt, Qt)-tuple for all t ∈ N , contradicting the hypotheses of the lemma. Consider now the case where u is a maximal (Pt, Qt)-tuple for all t ∈ (t * , t1). Then, for all t ∈ (t * , t1), there exists a line in Πt tangent to Pt and Qt and whose set of supports is u. Moreover, by Claim A, this line is unique for each t ∈ (t * , t1) and varies continuously in terms of t ∈ (t * , t1). When t tends to t * , the line tends to a line m in Πt * which is tangent to Pt * and Qt * and whose set of supports contains u. If its set of supports strictly contains u then m is tangent to Pt * and Qt * along an edge of one of them because the polygons are convex. Otherwise, u is a (Pt * , Qt * )-tuple.

We can suppose that u is a non-maximal (Pt * , Qt * )-tuple since we already treated the case where u is maximal. There exists in Πt * a line tangent to Pt * and Qt * whose set of supports is u. Since u is non-maximal this line is tangent to Pt * and Qt * at a shared vertex, and can be rotated about this vertex in Πt * until it gets tangent to Pt * and Qt * in some other points; let m denote the resulting line. The set of supports of m contains u and m is tangent to Pt * and Qt * along an edge of one of them because the polygons are convex. 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. 2

Claim E. Line m is tangent to P ∩ Ψ or to Q ∩ Ψ, at some point not on le.

Proof of Claim E. By Claim C, m is tangent to Qt * and thus to Q. It follows that m is tangent to Q ∩ Ψ or properly intersects it, in which case Q ∩ Ψ is a face or an edge of Q. If m is not tangent to Q ∩ Ψ at some point not on le then m is tangent to Q ∩ Ψ only on le, or Q ∩ Ψ is a face or an edge of Q. These two situations are not generic since 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 claim is straightforward under some general position assumption, however for polytopes in arbitrary position the proof is rather intricate and thus postponed to the appendix for the sake of clarity.2 This concludes the proof of Lemma 5.

Let I be any interval of /π (open or closed, reduced to a point or not). Lemma 6. Any edge or vertex of P or Q is in at most 2 PQ-tuples that are maximal (Pt, Qt)-tuples for all t in I.

Proof. Let t ∈ I and x be an edge or vertex of P or Q. If x does not intersect Πt then no (Pt, Qt)-tuple contains x. If x intersects Πt in one point then there is, in general, at most two lines in Πt going through x and tangent to Pt and Qt (see Figure 6(a)); in all cases there are at most 3 (Pt, Qt)tuples containing x (see Figure 6(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 Pt and Qt contains an endpoint of x and thus x belongs to no (Pt, Qt)-tuple.

Hence at most 2 PQ-tuples contain x and are maximal (Pt, Qt)-tuples for t = t and thus for all t in I. Lemma 7. There are at most O(p + q + r) PQR-tuples.

Proof. In order to count the number of distinct (Pt, Qt, Rt)-tuples, we charge each maximal (Pt, Qt, Rt)-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 4 that there are O(p + q + r) distinct maximal (Pt, Qt, Rt)-tuples. A maximal (Pt, Qt, Rt)-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 3 × 7 × 3 distinct subsets with at least one support in each of P, Q and R. Each maximal (Pt, Qt, Rt)-tuple thus contains at most 3 × 7 × 3 distinct (Pt, Qt, Rt)-tuples which implies the result.

Let s be a maximal (Pt, Qt, Rt)-tuple and let I be a maximal connected subset of /π such that s is a maximal (Pt, Qt, Rt)-tuple for all t ∈ I. Let u be a maximal (Pt, Qt)tuple and u a maximal (Qt, Rt)-tuple whose union is s and who share at least a support in Q.

If I = /π then u is a maximal (Pt, Qt)-tuple for all t ∈ I. Since u is maximal, the union of the supports in u intersects Πt in at least two distinct points. Moreover, each support in u intersects Πt for all t ∈ I and thus intersects le. It follows that le is the only line in Πt whose set of supports is u, for any t ∈ I. Similarly for u . Thus s is the set of supports of le. We can thus assume in the following that I = /π , and only count the maximal (Pt, Qt, Rt)-tuples that are not the set of support of le.

Interval I is thus a non-empty interval of /π ; it can be open or closed, reduced to a point or not. Let w0 and w1 denote its endpoints.

If s contains a vertex v, or an edge with endpoint v, such that v lies in Πw i \ le, for i = 0 or 1, then we charge s to the V-critical event (wi, v). Otherwise, we charge s to a F-critical event (wi, 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 5.

We now prove that each critical event is charged by at most a constant number of distinct maximal (Pt, Qt, Rt)tuples. As mentioned before, that will imply the result.

Consider a V-critical event (t * , v) that is charged by a maximal (Pt, Qt, Rt)-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 (Pt, Qt, Rt)-tuple for all t in at least one of three intervals, {t * } and two open intervals having t * as endpoint; denote by I1, I2, I3 these intervals.

By Lemma 6, at most 2 PQ-tuples contain x and are maximal (Pt, Qt)-tuples for all t in Ii. 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 (Qt, Rt)-tuples for all t in Ii. Thus at most 8 PQRtuples contain x and are maximal (Pt, Qt, Rt)-tuples for all t in Ii, for each i = 1, . . . , 3. Hence any V-critical event (t * , v) is charged by at most 24 distinct maximal (Pt, Qt, Rt)-tuples.

Consider now a F-critical event (t * , m) that is charged by a maximal (Pt, Qt, Rt)-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 (Pt, Qt, Rt)-tuple for all t in at least one of 3 intervals, {t * } and two open intervals having t * as endpoint; denote by I1, I2, I3 these intervals. It follows from Lemma 6 that, for each support x of Q in u, at most 2 QR-tuples contain x and are maximal (Qt, Rt)-tuples for all t in Ii. There are at most 3 2 choices for u, 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 (Pt, Qt, Rt)-tuples.

Therefore each critical event is charged by at most a constant number of distinct maximal (Pt, Qt, Rt)-tuples, which concludes the proof.

We now show in the next two lemmas that there are at most O(p + q + r) connected components of generic tangent lines. Lemma 8. The set of transversals to e and to the edges and vertices of a PQR-tuple contains at most O(1) connected components of tangents to P, Q, R and S.

Proof. The set of transversals to µ segments (possibly of zero length) consists of at most µ connected components [START_REF] Brönnimann | The number of transversals to line segments in 3[END_REF]. Since the union of {e} and any PQR-tuple consists of at most 8 segments (possibly of zero length), the result follows if the set of transversals to e and to the edges and vertices of a PQR-tuple is finite. We omit here the proof in the case where this set of transversals is not finite. Proposition 9. The generic tangent lines form O(p + q + r) connected components.

Proof. A generic tangent line is transversal to e and to the edges and vertices of a PQR-tuple, by definition and Lemma 3. Moreover, there are O(p + q + r) PQR-tuples by Lemma 7. The result thus follows from Lemma 8.

Nongeneric tangent lines

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

We first introduce some notation. A plane Πt is called a tangent plane if and only if it is tangent to P, Q, or R and at least one point of tangency does not lie on le. Lemma 10. A nongeneric tangent line lies in a tangent plane or properly intersects an edge of P, Q, or R lying in le.

Proof. Let be a nongeneric tangent line. By definition, properly intersects Pt, Qt, or Rt in some plane Πt. Suppose without loss of generality that properly intersects Pt. Since is tangent to P, Pt is a face or an edge of P which implies that Πt is tangent to P. Thus Πt is a tangent plane or Pt is an edge contained in le. In the first case, lies in the tangent plane Πt. In the latter case, properly intersects an edge of P lying in le.

We count first the nongeneric tangent lines lying in tangent planes and then the ones that properly intersect an edge of P, Q, or R lying in le.

Lemma 11. The nongeneric tangent lines lying in all tangent planes form O(p + q + r) connected components.

Proof. We first consider the nongeneric tangent lines lying in a given tangent plane Πt. Such lines intersect, properly or not, e, Pt, Qt, and Rt in the plane Πt. Let denote such a line and Ap (resp. At) the subset of {e, Pt, Qt, Rt} of polygons that properly intersect (resp. are tangent to

). We can move in Πt into a line tangent to at least two polygons of {e, Pt, Qt, Rt}, while intersecting (properly ot not) the polygons of Ap and remaining tangent to the polygons of At during the motion. There are O(p + q + r) such tangents, thus the nongeneric tangent lines lying in Πt form O(p + q + r) connected components. The result follows since there are at most 2 tangent planes per polytope.

Lemma 12. The nongeneric tangent lines that properly intersect an edge of P, Q, or R lying in le form O(p + q + r) connected components.

Proof. Let denote such a line. Let op be the union of edges of P that are contained in le; if no such edge exists, op is empty. We define oq and or similarly. Line intersects at least one of op, oq, and or. Let α = 1, 2, or 3 be the number of these sets intersected by . We consider in turn the three cases depending on the value of α. Case = 3. Sets op, oq, and or are all nonempty since intersects each of them. If op, oq, or and e do not all pairwise intersect, i.e., if I = e ∩ op ∩ oq ∩ or is empty then there is exactly one line intersecting all four op, oq, or and e, and that is line le. If on the contrary, I is nonempty, then the nongeneric tangent lines intersecting I are the line intersecting I and not intersecting the interior of P, Q, R and S. These lines thus form one connected component. Case = 2. Suppose that intersects op and oq; the other cases are similar. Then op and oq are nonempty. Again if I = e ∩ op ∩ oq is empty, then there is at most one line = le intersecting e, op, and oq and tangent to R. If on the contrary, I is nonempty then there are at most r edges of R that may induce some tangents with I. By Lemma 8, that implies that there are at most O(r) connected components of lines intersecting e, op, and oq, and tangent to P, Q, R and S. Case = 1. Suppose that intersects op; the other cases are similar. Then op is nonempty. Again if I = e ∩ op is empty, then there is at most one line = le intersecting both op and e and tangent to polytopes Q and R. Consider now the case where the common intersection I is nonempty. Lemmas 9, 10 and 11, when applied to I and the three polytopes Q, R, and again R yields that there are at most O(q + r) connected components of lines intersecting I and tangent to P, Q, R and S.

Lemmas 10, 11 and 12 yield the following result.

Lemma 13. There are at most O(p + q + r) connected components of nongeneric tangent lines.

This result together with Lemma 9 concludes the proof of the Main Lemma.

UPPER BOUND FOR THEOREM 2

We prove in this section the upper bound of Theorem 2 on the number of tangents to any 4 among k polytopes. The lower bound is proved in Section 4 Consider k polytopes P1,. . . , P k with n1,. . . , n k edges respectively. Let Pi, Pj , P l , and Pm be four pairwise distinct polytopes and e an edge of Pi. From the Main Lemma, we know that the number of connected components of lines intersecting e and tangent to Pi, Pj , P l , and Pm is no more than C(nj + n l + nm), where C is some constant. There are n edges in the scene, so the number T of connected components of tangents to four polytopes satisfies

T ¡ n ¢ j<l<m C (nj + n l + nm). Since each ni, 1 ¡ i ¡ k, appears £ k-1 2 ¤ times in the sum, T ¡ C n ¢ 1 ¥ i ¥ k ni ¦ k -1 2 § = C n 2 ¦ k -1 2 § so T is O(n 2 k 2 ) as claimed.

LOWER BOUNDS FOR THEOREMS 1 AND 2

We provide in this section the lower bounds needed for Theorems 1 and 2.

Lemma 14. There exist four disjoint polytopes of complexity O(n) such that the number of common tangent lines is finite and Ω(n 2 ). There also exist two polytopes of complexity O(n) and two polytopes of complexity O(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 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 7). 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 O(n) and two polytopes of complexity O(m).

We now provide the lower bound needed for Theorem 2.

Lemma 15. There exist k disjoint polytopes of total complexity O(n) such that the number of non-occluded maximal line segments tangent to four of them is finite and Ω(k 2 n 2 ).

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 A1 in the plane x = 0. Next we consider a copy, B0, of A1 scaled by a factor of (1 + ε), and on each edge of B0 we place k 4 points. Polygon Bi, 1 1 + i k ε (see Figure 8). For the moment, all polygons lie in plane x = 0. We now construct 4 families of k 4 polygons each: -Pi is a copy of Ai translated by i in the negative x direction -Qi is a copy of Bi translated by i in the positive x direction -Ri is a copy of Bi translated by 1i in the positive x direction -Si is a copy of Ai translated by 1 + i in the positive x direction Any choice of four polygons, one in each family Pi, Qj, R l and Sm, reproduces the quadratic example of Lemma 14 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 Pi, Qj, R l and Sm 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 14. Proof. First if m = le then mt = le for all t ∈ N because Ψ contains m = le (by Claim D) and Πt contains le for all t (by definition). Thus the set of supports of mt is invariant for all t ∈ N . We now assume that m = le.

Ψ m = Π t * ∩ Ψ Π t * +ε ∩ Ψ Π t * -ε ∩ Ψ le face of P in Ψ face of Q in Ψ (a) (b) Ψ m = Π t * ∩ Ψ Π t * +ε ∩ Ψ Π t * -ε ∩ Ψ Q ∩ Ψ le face of P in Ψ
Line m is tangent to polygon Pt * along an edge by Claim C. 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 le since m = le, thus m is tangent to P ∩ Ψ at some point not on le, 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 mt for all t in any sufficiently small open neighborhood of t * (indeed mt lies in Ψ and tends to m when t tends to t * ). By Lemma 16, the set of supports of mt 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 * \ le, thus m contains no vertex of P except possibly on le (since m lies in Πt * ). It thus follows that the set of supports of mt in P is invariant for t ranging in any sufficiently small open neighborhood of t * (since mt ⊂ Ψ 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 le and thus the set of supports of mt 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 le. Then, as in the proof of Lemma 16, the set of supports of mt in Q is invariant for all t ranging in any sufficiently small open neighborhood of t * , which concludes the proof.

Proof of Claim E. It follows from Lemmas 16 and 17 that the set of supports of mt is invariant and equal to u for all t ∈ N . Moreover, since mt varies continuously with t and m = mt * is tangent to Pt * and Qt * (by Claim C), line mt is tangent to Pt and Qt for all t ∈ N . Hence u is a (Pt, Qt)-tuple for all t ∈ N . We now prove that u is a maximal (Pt, Qt)-tuple for all t ∈ N .

As we have seen before, m = mt * is tangent to P in at least two points (by Claim C), thus mt * intersects its supports in at least two distinct points. Moreover the set of supports of mt * is u. Thus there is a unique line in Πt * whose set of supports contains u. Hence u is a maximal (Pt * , Qt * )-tuple.

By Claim A, mt is the unique line in Πt whose set of supports contains u for all t = t * in N . Thus u is a maximal (Pt, Qt)-tuple for all t = t * in N .

Hence u is a maximal (Pt, Qt)-tuple for all t ∈ N , contradicting the hypotheses of Lemma 5 and thus concluding the proof of Claim E. The set u of supports of line Πt * -ε ∩ Ψ is a maximal (Pt, Qt)-tuple for some but not all t in any open neighborhood of t * . There is a F-critical event (t * , m) (where m = Πt * ∩ Ψ) such that u is contained in the set of supports of m because (i) m lies in plane Ψ = Πt * containing a face of P and (ii) m is tangent to P ∩ Ψ at some point not on le. Note that there is no V-critical event (t * , v) such that u contains v or an edge with endpoint v, and there is no line ∈ Πt * such that (i) lies in a plane Υ = Πt * containing a face of P and (ii) is tangent to Q ∩ Υ at some point not on le; indeed is necessarily equal to m, if Υ = Ψ then is not tangent to Q ∩ Υ and we can consider that the plane, distinct from Ψ, that contains and a face of P is equal to Πt * .

Figure 1 :

 1 Figure 1: A terrain of size O(n) with Ω(n 4 ) maximal non-occluded line segments tangent in four points.

Figure 2 :

 2 Figure 2: Plane Πt contains edge e and intersects polytopes P, Q, and R in polygons Pt, Qt, and Rt, respectively.

Figure 3 :

 3 Figure 3: A bitangent to Pt and Qt is tangent to Pt along an edge. The plane Πt is F-critical.

Figure 4 :

 4 Figure 4: Plane Πt contains a line that is tangent to Q and lies in a plane containing a face of P. Plane Πt is F-critical.

Figure 5 :

 5 Figure 5: m is tangent to P along a face in plane Ψ = Πt * .

2

 2 Claim C. There exists a line m in Πt * whose set of supports contains u that is tangent to Pt * and Qt * along an edge of one of them, say of Pt * . Proof of Claim C. Consider first the case where u is a maximal (Pt * , Qt * )-tuple. There exists in Πt * a line m tangent to Pt * and Qt * whose set of supports is u. By Claim B, the set u of supports of m contains 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 Pt * (or Qt * ) in at least two distinct points and is tangent to Pt * and Qt * . The result follows since Pt * (and Qt * ) is convex.

2 Figure 6 :

 26 Figure 6: Lines through x in Πt and tangent to Pt and Qt.

Figure 7 :

 7 Figure 7: Lower bound example for Lemma 14.

1 B 2 B 3 B 0 A 2 A 1 Figure 8 :

 1230218 Figure 8: The polygons Ai and Bi.

Figure 9 :

 9 Figure 9: m is tangent to P along a face in Ψ and (a) to Q ∩ Ψ only on le or (b) to Q along a face in Ψ.

Figure 10 :

 10 Figure10: The set u of supports of line Πt * -ε ∩ Ψ is a maximal (Pt, Qt)-tuple for some but not all t in any open neighborhood of t * . There is a F-critical event (t * , m) (where m = Πt * ∩ Ψ) such that u is contained in the set of supports of m because (i) m lies in plane Ψ = Πt * containing a face of P and (ii) m is tangent to P ∩ Ψ at some point not on le. Note that there is no V-critical event (t * , v) such that u contains v or an edge with endpoint v, and there is no line ∈ Πt * such that (i) lies in a plane Υ = Πt * containing a face of P and (ii) is tangent to Q ∩ Υ at some point not on le; indeed is necessarily equal to m, if Υ = Ψ then is not tangent to Q ∩ Υ and we can consider that the plane, distinct from Ψ, that contains and a face of P is equal to Πt * .

  [START_REF] Berg | Sparse arrangements and the number of views of polyhedral scenes[END_REF]

	le	face of P in Ψ
		edge of Q in Ψ
			Π t * +ε ∩ Ψ
			m = Π t * ∩ Ψ
	edge of P	Π t * -ε ∩ Ψ
	Ψ
	le
		Q t * +ε
	P t * +ε
		Π t * +ε ∩ Ψ
	Π t * +ε
	le
	P t *	Q t *
		m = Π t * ∩ Ψ
	edge of P
	Π t *
	le
	P t * -ε	Q t * -ε
		Π t * -ε ∩ Ψ
	Π t * -ε

This simple argument actually only holds for extremal tangent lines ; for the general argument, see the full paper.

[START_REF] Brönnimann | The number of transversals to line segments in 3[END_REF] A line properly intersects a polygon if and only if it intersects its relative interior.

For simplicity, we prove Lemma 5 under the assumptions that u is maximal and distinct from ue; note however that the lemma remains correct without these assumptions.

APPENDIX Proof of Claim E

We give here a complete proof of Claim E of Lemma 5 when the polytopes are in arbitrary position. We first recall the claim.

Claim E. Line m is tangent to P ∩ Ψ or to Q ∩ Ψ, at some point not on le.

In the following, we keep all the notation and assumptions made in the proof of Lemma 5 and all the claims that are referred to are those of Lemma 5.

We assume for a contradiction that line m does not satisfy Claim E, i.e., m is not tangent to P ∩ Ψ or to Q ∩ Ψ at any point other than on le. We prove that the set of supports of m is u and is a maximal (Pt, Qt)-tuple for all t in any sufficiently small neighborhood of t * , contradicting the hypotheses of Lemma 5.

Since m is tangent to Q (by Claim C), m is tangent to Q ∩ Ψ only on le (see Figure 9(a)), or m properly intersects Q ∩ Ψ which is then a face or an edge of Q (see Figure 9(b)). Similarly m is tangent to P ∩ Ψ only on le, or m properly intersects it; however P ∩ Ψ is necessarily a face of P by Claim D.

Let mt be the line Ψ ∩ Πt for all t in any sufficiently small open neighborhood N of t * ; line mt is well defined since Ψ ∩ Πt * is line m by Claims C and D. Recall that we only consider here supports in P and Q.

Lemma 16. The set of supports of mt is u for some t in any sufficiently small open neighborhood N of t * .

Proof. We first prove that the supports in u are supports of mt for all t ∈ N . A support vertex in u lies on le by Claim A and thus lies in Πt for all t. A support vertex in u also lies on m by Claim C and thus lies in plane Ψ by Claim D. Hence, for all t ∈ N , the support vertices in u lie on mt, and thus are supports of mt.

In order to prove that the support edges in u are supports of mt, it is sufficient (by Claim C) to prove that the support edges of m are supports of mt. The support edges of m in P lie in plane Ψ (see Figure 9(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 mt lies in Ψ for all t and mt * = m, line mt 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 mt 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 mt for all t ∈ N .

Consider now the case where m is tangent to Q ∩ Ψ only on le at, say, point v (see Figure 9(a)). Then v lies in Ψ (since m ⊂ Ψ by Claim D) and also lies in Πt for all t (since le ⊂ Πt for all t). Hence mt contains v for all t ∈ N . Moreover, mt 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 mt in Q is invariant for all t ∈ N .

We have so far proved that the set of supports of mt contains u for all t ∈ N .

We now prove that the set of supports of mt is u for some t ∈ N . Consider first the case where u is a maximal (Pt * , Qt * )-tuple. Then, by Claim A, the union of the supports in u intersects Πt * in at least two distinct points, thus mt * = m is the only line in Πt * whose set of supports contains u. Moreover, since u is a (Pt * , Qt * )-tuple, there exists a line in Πt * whose set of supports is u. Hence the set of supports of mt * is u.

Consider now the case where u is a maximal (Pt, Qt)-tuple for all t ∈ (t * , t1). By Claim A, for all t ∈ (t * , t1), the union of the supports in u intersects Πt in at least two distinct points, thus mt is the only line in Πt whose set of supports contains u. For all t ∈ (t * , t1), since u is a (Pt, Qt)-tuple there exists a line in Πt whose set of supports is u. Hence the set of supports of mt is u for all t ∈ (t * , t1). Lemma 17. The set of supports of mt is invariant for t ranging in any sufficiently small open neighborhood N of t * .