Approximating the k-Level in Three-Dimensional Plane Arrangements∗ Sariel Har-Peled† Haim Kaplan‡ Micha Sharir§ May 18, 2016 6 1 0 2 Abstract y a Let H be a set of n non-vertical planes in three dimensions, and let r < n be a parameter. M We give a simple alternative proof of the existence of an O(1/r)-cutting of the first n/r levels of A(H), which consists of O(r) semi-unbounded vertical triangular prisms. The same construction 7 1 yields an approximation of the (n/r)-level by a terrain consisting of O(r/ε3) triangular faces, which lies entirely between the levels n/r and (1+ε)n/r. The proof does not use sampling, and ] G exploits techniques based on planar separators and various structural properties of levels in three- C dimensional arrangements and of planar maps. The proof is constructive, and leads to a simple . randomized algorithm, that computes the approximating terrain in O(n + rε 6log3r) expected s − c time. An application of this technique allows us to mimic and extend Matouˇsek’s construction [ of cuttings in the plane [Mat90], to obtain a similar construction of a “layered” (1/r)-cutting of 2 the entire arrangement A(H), of optimal size O(r3). Another application is a simplified optimal v approximate range counting algorithm in three dimensions, competing with that of Afshani and 5 5 Chan [AC09a]. 7 4 0 1. Introduction . 1 0 6 A tribute to Jirka Matouˇsek. We were very fortunate to have Jirka as a friend and colleague. He 1 has entered our community in the late 1980’s, and has been a giant lighthouse ever since, showing us : v the way into new discoveries, solving mysteries for us, and just providing us with new tools, ideas, and i X techniques, that have made our work much more interesting and productive. He has been everywhere, r making seminal contributions to so many topics in computational and discrete geometry (and to other a fields too). We have been avid readers of his many books, most notably Lectures on Discrete Geometry, A preliminary version of this paper appeared in Proc. 27th Annu. ACM-SIAM Sympos. Discrete Algs. (SODA), ∗ 2016, 1193–1212[HKS16]. WorkbySarielHar-PeledwaspartiallysupportedbyNSFAFawardsCCF-1421231andCCF- 1217462. WorkbyHaimKaplanwaspartiallysupportedbygrant1161/2011fromtheGerman-IsraeliScienceFoundation, bygrant822/10fromtheIsraelScienceFoundation,andbytheIsraeliCentersforResearchExcellence(I-CORE)program (center no. 4/11). Work by Micha Sharir has been supported by Grant 2012/229 from the U.S.-Israel Binational Science Foundation,byGrant892/13fromtheIsraelScienceFoundation,bytheIsraeliCentersforResearchExcellence(I-CORE) program (center no. 4/11), and by the Hermann Minkowski–MINERVA Center for Geometry at Tel Aviv University. Department of Computer Science, University of Illinois, 201 N. Goodwin Avenue, Urbana, IL, 61801, USA. E-mail: † [email protected]; url: http://sarielhp.org/ School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel. E-mail: [email protected] ‡ School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel. E-mail: [email protected] § 1 andhavebeenadmiringhisclearyetprecisestyleofexpositionandpresentation. Wehavealsolearnedto appreciate his personality, his dry but touching sense of humor, his love for nature, his infinite devotion to science on one hand, and to his family and friends on the other hand. His departure has been painful to us, and we will miss him badly. We thank you, Jirka, for all the gifts you gave us, and may your soul be blessed. This paper is about a topic that Jirka has worked on, rather extensively, during the early 1990s, concerning cuttings and related techniques for decompositions of arrangements or of point sets, and their applications to range searching and other algorithmic and combinatorial problems in geometry. In particular, in 1992 he has written a seminal paper on “Reporting points in halfspaces” [Mat92c], where he introduced and analyzed shallow cuttings, a technique that had many applications during the following decades. In a later paper, following his earlier work [Mat90] (probably his first entry into computational geometry), Jirka [Mat98] presented a construction of (1/r)-cuttings, for a set of lines in the plane, with ≤ 8r2 + 6r + 4 cells. This construction uses, as a basic building block, a strikingly simple procedure for approximating a level in a line arrangement: Since a specific level is an x-monotone polygonal chain, one can pick every q-th vertex, for q ≈ n/r, and connect these vertices consecutively to form an approximate level, which is at crossing distance at most q/2 from the original level. As is well known, this construction is asymptotically optimal for any arrangement of lines in general position. This elegant level approximation algorithm, in two dimensions, raises the natural question of whether one can approximate a level in three dimensions for a given set of planes, by an xy-monotone polyhedral terrain constructed directly, in an analogous manner, from the original level. This paper provides an affirmative answer to this question, thereby pushing Jirka’s work further, for the special case of three-dimensional arrangements of planes. It refines the shallow cuttings technique of [Mat92c], and applies it to obtain cleaner and more efficient solutions for several related problems. Our new scheme for approximating a level by a terrain, while significantly more involved than Jirka’s two-dimensional construction, still echoes and generalizes his basic idea of “shortcutting” the original level by a coarser triangular mesh (instead of a simplified polygonal chain) spanned by selected vertices of the level. Cuttings. Let H be a set of n (non-vertical) hyperplanes in Rd, and let r < n be a parameter. A (1/r)-cutting of the arrangement A(H) is a collection of pairwise openly disjoint simplices (or other regions of constant complexity) such that the closure of their union covers Rd, and each simplex is crossed (meets in its interior) at most n/r hyperplanes of H. Cuttings have proved to be a powerful tool for a variety of problems in discrete and computa- tional geometry, because they provide an effective divide-and-conquer mechanism for tackling such problems; see Agarwal [Aga91a] for an early survey. Applications include a variety of range searching techniques [AE99], partition trees [Mat92a], incidence problems involving points and lines, curves, and surfaces [CEG+90], and many more. The first (albeit suboptimal) construction of cuttings is due to Clarkson [Cla87]. This concept was formalized later on by Chazelle and Friedman [CF90], who gave a sampling-based construction of optimal-size cuttings (see below). An optimal deterministic construction algorithm was provided by Chazelle [Cha93]. Matouˇsek [Mat98] studied the number of cells in a (1/r)-cutting in the plane (see also [Har00]). See Agarwal and Erickson [AE99] and Chazelle [Cha04] for comprehensive reviews of this topic. To be effective, it is imperative that the number of simplices in the cutting be asymptotically as small as possible. Chazelle and Friedman [CF90] were the first to show the existence of a (1/r)-cutting of the 2 entire arrangement of n hyperplanes in Rd, consisting of O(rd) simplices, which is asymptotically the best possible bound. (We note in passing that cuttings of optimal size are not known for arrangements of (say, constant-degree algebraic) surfaces in Rd, except for d = 2, where the known bound, O(r2), is tight, and for d = 3,4, where nearly tight bounds, nearly cubic and quartic in r, respectively, are known [CEGS91, Kol04, KS05].) For additional works related to cuttings and their applications, see [AC09b, ACT14, AT14, Aga90a, Aga90b, Aga91b, AACS98, Mat92a, Mat92b, CT15, AT14, Har00, Ram99]. Shallow cuttings. The level of a point p in the arrangement A(H) of H is the number of hyperplanes lying vertically below it (that is, in the (−x )-direction). For a given parameter 0 ≤ k ≤ n − 1, the d k-level, denoted as L , is the closure of all the points that lie on some hyperplane of H and are at k level exactly k, and the (≤ k)-level, denoted as L , is the union of all the j-levels, for j = 0,...,k. k ≤ A collection of pairwise openly disjoint simplices such that the closure of their union covers L , and k ≤ such that each simplex is crossed at most n/r hyperplanes of H, is called a k-shallow (1/r)-cutting. Naturally, the parameters k and r can vary independently, but the interesting case, which is the one that often arises in many applications, is the case where k = Θ(n/r). In fact, shallow cuttings for any value of k can be reduced to this case—see Chan and Tsakilidis [CT15, Section 5]. In his seminal paper on reporting points in halfspaces [Mat92c], Matouˇsek has proved the existence of small-size shallow cuttings in arrangements of hyperplanes in any dimension, showing that the bound on the size of the cutting can be significantly improved for shallow cuttings. Specifically, he has shown the existence of a k-shallow (1/r)-cutting, for n hyperplanes in Rd, whose size is O(cid:0)q d/2 r d/2 (cid:1), where (cid:100) (cid:101) (cid:98) (cid:99) q = k(r/n)+1. For the interesting special case where k = Θ(n/r), we have q = O(1) and the size of the (cid:0) (cid:1) cutting is O r d/2 , a significant improvement over the general bound O(rd). (For example, in three (cid:98) (cid:99) dimensions, we get O(r) simplices, instead of O(r3) simplices for the whole arrangement.) This has lead to improved solutions of many range searching and related problems. In his paper, Matouˇsek presented a deterministic algorithm that can construct such a shallow cutting in polynomial time; the running time improves to O(nlogr) but only when r is small, i.e., r < nδ for a sufficiently small constant δ (that depends on the dimension d). Later, Ramos [Ram99] presented a (rather complicated) randomized algorithm for d = 2,3, that constructs a hierarchy of shallow cuttings for a geometric sequence of O(logn) values of r, where for each r the corresponding cutting is a (1/r)- cutting of the first Θ(n/r) levels of A(H). Ramos’s algorithm runs in O(nlogn) total expected time. Recently, Chan and Tsakalidis [CT15] provided a deterministic O(nlogr)-time algorithm for computing an O(n/r)-shallow (1/r)-cutting. Their algorithm can also construct a hierarchy of shallow cuttings for a geometric sequence of O(logn) values of r, as above, in O(nlogn) deterministic time. Interestingly, they use Matouˇsek’s theorem on the existence of an O(n/r)-shallow (1/r)-cutting of size O(r) in the analysis of their algorithm. Each simplex ∆ in the cutting has a conflict list associated with it, which is the set of hyperplanes intersecting ∆. The algorithms mentioned above for computing cuttings also compute the conflict lists associated with the simplices of the cutting. Alternatively, given the cutting, one can produce the conflict lists in O(nlogr) time using a result of Chan [Cha00], as we outline in Section 3.2. Matouˇsek’s proof of the existence of small-size shallow cuttings, as well as subsequent studies of this technique, are fairly complicated. They rely on random sampling, combined with a clever variant of the so-called exponential decay lemma of [CF90], and with several additional (and rather intricate) techniques. 3 Approximating a level. An early study of Matouˇsek [Mat90] gives a construction of a (1/r)-cutting of small (optimal) size in arrangements of lines in the plane. The construction chooses a sequence of r levels, n/r apart from one another, and approximates each of them by a coarser polygonal line, by choosing every n/(2r)-th vertex of the level, and by connecting them by an x-monotone polygonal path. Each approximate level does not deviate much from its original level, so they remain disjoint from one another. Then, partitioning the region between every pair of consecutive approximate levels into vertical trapezoids produces a total of O(r2) such trapezoids, each crossed by at most O(n/r) lines. Itisthusnaturaltoaskwhetheronecanapproximate,inasimilarfashion,ak-levelofanarrangement of planes in 3-space. This is significantly more challenging, as the k-level is now a polyhedral terrain, and while it is reasonably easy to find a good (suitably small) set of vertices that “represent” this level (in an appropriate sense, detailed below), it is less clear how to triangulate them effectively to form an xy-monotone terrain, such that (i) none of its triangles is crossed by too many planes of H, and (ii) it remains close to the original level. To be more precise, given k and ε > 0, we want to find a polyhedral terrain with a small number of faces, which lies entirely between the levels k and (1+ε)k of A(H). A simple tweaking of Matouˇsek’s technique produces such an approximation in the planar case, but it is considerably more involved to do it in 3-space. Algorithms for terrain approximation, such as in [AD97], do not apply in this case, as they have a quadratic blowup in the output size, compared to the optimal approximation. Also, they are not geared at all to handle our measure of approximation (in terms of lying close to a specified level, in the sense that no point on the approximation is separated by too many planes from the level). Such an approximation to the k-level, whose size is optimal up to polylogarithmic factors, can be obtained by using a relative-approximation sample of the planes, and by extracting the appropriate level in the sample [HS11]. A more natural approach, of using the triangular faces of an optimal-size shallow cutting to form an approximate k-level, seems to fail in this case, as the shallow cutting is in general just a collection of simplices, stacked on top of one another, with no clearly defined xy-monotonicity. Such a monotonicity is obtained in Chan [Cha05], by replacing a standard shallow cutting by a suitable upper convex hull of its simplices. However, the resulting cuttings do not lead to a sharp approximation of the level, of the sort we seek. In short, a simple, effective, and optimal technique for approximating a level in three dimensions (let alone in higher dimensions) does not follow easily from existing techniques. An additional advantage of such an approximation is that it immediately yields a simply-shaped shallow cutting of the first k levels of A(H), by replacing each triangle ∆ of the approximate level by the vertical semi-unbounded triangular prism ∆ having ∆ as its top face, and consisting of all ∗ points that lie on or vertically below ∆. Such a cutting (by prisms) has already been constructed by Chan [Cha05], but it does not yield (that is, come from) a (1+ε)-approximation to the level. Such a shallow cutting, by vertical semi-unbounded triangular prisms, was a central tool in Chan’s algorithm for dynamic convex hulls in three dimensions [Cha10]. Thus,resolvingthequestionofapproximatingthek-levelbyanxy-monotoneterrainofsmall,optimal size is not a mere technical issue, but rather a tool that will shed more light on the geometry of arrangements of planes in three dimensions, and that has applications to a variety of problems. For example, it yields an efficient algorithm for approximating the level of a point in an arrangement of planes in R3, which is the dual version of approximate halfspace range counting—see Section 4.2 for details. (Afshani and Chan [AC09a] present a similar approach to approximating the level which is slightly more involved, as they do not have the desired terrain property.) 4 1.1. Our results In this paper we give an alternative, simpler and constructive proof of the existence of optimal-size shal- low cuttings in a three-dimensional plane arrangement, by vertical semi-unbounded triangular prisms. With a bit more care, the construction yields an optimal-size approximate level, as discussed above. Specifically, given r and ε, one can approximate the (n/r)-level in an arrangement of n non-vertical planes in R3, by a polyhedral terrain of complexity O(r/ε3), that lies entirely between the levels n/r and (1+ε)n/r. The same construction works for any values of the level k and the parameter r ≤ n/k, with a somewhat more involved bound on the complexity of the approximation. The construction does not use sampling, nor does it use the exponential decay lemma of [CF90, Mat92c]. It is based on the planar separator theorem of Lipton and Tarjan [LT79], or, more precisely, on recent separator-based decomposition techniques of planar maps, as in Klein et al. [KMS13] (see also Frederickson [Fre87]), and on several insights into the structure and properties of levels in three dimensions and of planar maps, which we believe to be of independent interest. As what we believe to be an interesting application of our technique, we extend Matouˇsek’s construc- tion [Mat90] of cuttings in planar arrangements to three dimensions. That is, we construct a “layered” (1/r)-cutting of the entire arrangement A(H) of a set H of n non-vertical planes in R3, of optimal size O(r3), by approximating each level in a suitable sequence of levels, and then by triangulating each layer between consecutive levels in the sequence. The analysis becomes considerably more involved in three dimensions, and requires several known but interesting and fairly advanced properties of plane arrangements. Another application of our technique is to approximate range counting. Specifically, we show how to preprocess a set H of n non-vertical planes in R3, and a prescribed error parameter ε > 0, in near-linear time (in n), into a data structure of size O(n/ε8/3), so that, given a query point q ∈ R3, we can compute the number of planes of H lying below q, up to a factor 1 ± ε, in O(log(n/(εk))) expected time. As noted, this competes with Afshani and Chan’s technique [AC09a]. The general approach is similar in both solutions, but our solution is somewhat simpler, due to the availability of approximating terrains, andthedependenceonεinoursolutionisexplicitandreasonable(thisdependenceisnotgivenexplicitly in [AC09a]). The thrust of this paper is thus to show, via alternative, simpler, and more geometric methods, the existence of cuttings and approximate levels of optimal size. The proofs are constructive, but naive implementations thereof would be rather inefficient. Nevertheless, using standard random sampling techniques, we can obtain simple randomized algorithms that perform (suitable variants of) these con- structions efficiently. Specifically, they run in near-linear expected time (which becomes linear when r is not too large). Sketch of our technique. The k-level in a plane arrangement in three dimensions is an xy-monotone polyhedral terrain. After triangulating each of its faces, its xy-projection forms a (straight-edge) trian- gulated biconnected planar map. Since the average complexity of the first k levels is O(nk2) (see, e.g., [CS89]), we may assume, by moving from a specified level to a nearby one, that the complexity of our level is O(nk). The decomposition techniques of planar graphs mentioned above (as in [KMS13]) allow us to partition the level into O(n/k) clusters, where each cluster has O(k2) vertices and O(k) boundary vertices (vertices that also belong to other clusters). In the terminology of [KMS13], this is a k2-division of the graph. Each such cluster, projected to the xy-plane, is a polygon with O(k) boundary edges (and with O(k2) interior edges). We show that, replacing each such projected polygon by its convex hull results in a collection of O(n/k) convex pseudo-disks, namely, each hull is (trivially) simply connected, and the boundaries of any pair of hulls intersect at most twice. Moreover, the decomposition has the 5 property that, for each triangle ∆ that is fully contained in such a pseudo-disk, lifting its vertices back to the k-level yields a triple of points that span a triangle ∆ with a small number of planes crossing it, (cid:48) so it lies close to the k-level. An old result of Bambah and Rogers [BR52], proving a statement due to L. Fejes-T´oth, and reviewed in [PA95, Lemma 3.9] (and also briefly below), shows that a union of m convex pseudo-disks that covers theplaneinducesatriangulationoftheplanebyO(m)triangles, suchthateachtriangleisfullycontained inside one of the pseudo-disks. (As a matter of fact, it shows that each pseudo-disk can be shrunk into convex polygon so that these polygons are pairwise openly disjoint, with the same union, and the total number of edges of the polygons is at most 6m; the desired triangulation is obtained by simply triangulating, arbitrarily, each of these polygons.) Lifting (the vertices of) this triangulation to the k-level, with a corresponding lifting of its triangular faces, results in the desired terrain approximating the level. A significant technical contribution of this paper is to provide an alternative proof of this result. The original proof in [BR52] appears to be fairly involved, although its presentation in [PA95] is simplified. Still, it does not seem to lead to a sufficiently efficient construction. Our proof in contrast does lead to such a construction, as described in Section 2. A shallow cutting of the first k levels is obtained by simply replacing each triangle ∆ in the approx- imate level by the semi-unbounded vertical prism of points lying below ∆. Confined triangulations. The idea of decomposing the union of objects (pseudo-disks here) into pairwiseopenlydisjointsimply-shapedfragments, eachfullycontainedinsomeoriginalobject, isimplicit in algorithms for efficiently computing the union of objects; see the work of Ezra et al. [EHS04], which was in turn inspired by Mulmuley’s work on hidden surface removal [Mul94]. Mustafa et al. [MRR14] use a more elaborate version of such a decomposition, for situations where the objects are weighted. While these decompositions are useful for a variety of applications, they still suffer from the problem that the complexity of a single region in the decomposition might be arbitrarily large. In contrast, the triangulation scheme that we use (following [BR52]) is simpler, optimal, and independent of the complexity of the relevant pseudo-disks. We are pleased that this nice property of convex pseudo-disks is (effectively) applicable to the problems studied here, and expect it to have many additional potential applications. In particular, we extend our analysis, and show that such a decomposition exists for arbitrary convex shapes, with the number of pieces being proportional to the union complexity, and with each region being a triangle or a cap (i.e., the intersection of an input shape with a halfplane). This provides a representation of “most” of the union by triangles, where the more complicated caps are only used to fill in the “fringe” of the union (and are absent when the union covers the entire plane, as in [BR52]). We believe that this triangulation could be useful in practice, in situations where, given a query point q, one wants to decide whether q is inside the union, and if so, provide a witness shape that contains q. For this, we simply locate the triangle in our triangulation that contains q, from which the desired witness shape is immediately available. This is significant in situations where deciding whether a point belongs to an input shape is considerably more expensive than deciding whether it lies inside a triangle. Paper organization. We start by presenting the construction of the confined triangulation in Sec- tion 2. We then describe the construction of approximate levels, and the construction of shallow cuttings that it leads to, in Section 3. We then present applications of our results in Section 4. Specifically, in Section 4.1 we show how to build a layered cutting of the whole arrangement, and in Section 4.2 we show how to answer approximate range counting queries for halfspaces. 6 2. Triangulating the union of convex shapes In this section we show that, given a finite collection of m convex pseudo-disks covering the plane, one can construct a triangulation of the plane, consisting of O(m) triangles, such that each triangle is contained in a single original pseudo-disk—see Theorem 2.4 below for details. Our result can be extended to situations where the union of the pseudo-disks is not the entire plane; see below. This claim is a key ingredient in our construction of approximate k-levels, detailed in Section 3, but it is not new, as it is an immediate consequence of an old result of Bambah and Rogers [BR52] (proving a statement by L. Fejes-To´th), whose proof is sketched below. Bambah and Rogers’ proof. For the sake of completeness, we briefly sketch the q proof of Bambah and Rogers (as presented in Pach and Agarwal [PA95, Lemma 3.9]). Let K be a collection of m polygonal convex pseudo-disks in the plane, and C p D assume, for simplicity, that their union is a triangle T (extending this simplest scenario to the more general case is straightforward). We may also assume that no pseudo-disk of K is contained in the union of the other regions of K, as one can simply throw away any such redundant pseudo-disk. Finally, since the construction will create regions with overlapping boundaries, we use the more general definition of pseudo-disks, requiring, for each pair C,D ∈ K, that C \D and D\C are both connected. Let C and D be two pseudo-disks of K, such that the common intersection q C int(C)∩int(D) of their interiors is nonempty and minimal in terms of containment 0 (that is, it does not contain any other such intersection). Let p and q be the two p D intersection points of ∂C and ∂D (assume for simplicity that ∂C and ∂D do not 0 E overlap, making p and q well defined). Cut C and D along the segment pq, and let C ⊆ C and D ⊆ D be the two resulting pieces whose union is C∪D. Let K = (K\{C,D})∪{C ,D }. (cid:48) (cid:48) (cid:48) (cid:48) (cid:48) The claim is that K is a collection of m pseudo-disks covering T. (cid:48) Indeed, consider a pseudo-disk E ∈ K other than C , D . We need to show E D that E \ C and C \ E are both connect(cid:48)ed, and similar(cid:48)ly f(cid:48)or E and D . If E E C0 ∩ (cid:48) (cid:48) (cid:48) contains p (resp., q), then it is easy to verify, by convexity, that E and C are (cid:48) C D D pseudo-disks, and similarly for E and D . Assume then E does not contain p or ∩ 0 (cid:48) q, but still intersects the segment pq. By assumption, E \(C ∪D) is not empty, so we may assume, without loss of generality, that E intersects the boundary of ∂C \ D. But then E ∩D ⊆ C ∩D, as otherwise E would intersect the boundary of C in four points, which is impossible. This in turn contradicts the minimality of C ∩D. We thus replace K by K, and repeat this process till all the pseudo-disks in the resultimg collection (cid:48) are pairwise interior disjoint. At this point, K is a pairwise openly disjoint cover of the triangle T, by m convex polygons (each contained inside its original pseudo-disk). By Euler’s formula, these polygons can be triangulated into O(m) triangles with the desired property. This elegant proof is significantly simpler than what follows, but it does not seem to lead to an efficient algorithm for constructing the desired triangulation in near-linear running time. We present here a different alternative (efficiently) constructive proof, which leads to an O(mlogm)-time algorithm for constructing the triangulation for a set of m pseudo-disks, in a suitable model of computation. (As an aside, we also think that such a nice property deserves more than one proof.) We also establish an extension of this result to more general convex shapes. 7 Figure 2.1: A union of three disks, and its decomposition into triangles and caps. Note that the decomposition computed by our algorithm is somewhat different for this case. 2.1. Preliminaries The notion of a triangulation that we use here is slightly non-standard, as it might be a triangulation of the entire plane, and not just of the convex hull of some input set cap of points. As such, it contains unbounded triangles, where the boundary of each such triangle consists of one bounded segment and two unbounded rays (where the segment might degenerate into a single point, in which case the triangle becomes a wedge). Given a convex shape D, a cap of D is the region formed by the intersection of D with a nt e c halfplane. A crescent is a portion of a cap obtained by removing from it a convex polygon es cr that has the base chord of the cap as an edge, but is otherwise contained in the interior of the cap. Definition 2.1. Given a collection D of convex shapes in the plane, a decomposition T of their union into pairwise openly disjoint regions is a confined triangulation, if (i) every region in T is either a triangle or a cap, and (ii) every such region is fully contained in one of the original input shapes. See Figure 2.1 for an example of a confined triangulation. 2.2. Construction We are given a collection D of m convex pseudo-disks, and our goal is to construct a confined triangula- tion for D, as described above, with O(m) pieces. In what follows we consider both the case where the union of D covers the plane, and the case where it does not. 2.2.1. Painting the union from front to back. A basic property of a collection D of m pseudo- (cid:83) disks is that the combinatorial complexity of the boundary of the union U := U(D) = C of D C is at most 6m − 12, where we ignore the complexity of individual members of D, and just∈cDount the number of intersection points of pairs of boundaries of members of D that lie on ∂U; see [KLPS86]. For convenience, we also (i) include the leftmost and rightmost points of each D ∈ D in the set of intersection points (if they lie on the union boundary), thus increasing the complexity of the union by at most 2m, and (ii) assume general position of the pseudo-disks. In general, an intersection point v of a pair of boundaries is at depth k (of the arrangement A(D) of D) if it is contained in the interiors of exactly k members of D. The boundary intersections are thus at depth 0, and a simple application of the Clarkson–Shor technique [CS89] implies that the number of boundary intersection points that lie at depth 1 is also O(m). Hence there exists at least one pseudo-disk D ∈ D that contains at most c 8 2 2 2 4 1 1 1 1 3 3 4 (1) (2) (3) (4) 2 2 2 4 1 1 1 1 3 3 4 (1’) (2’) (3’) (4’) 5 6 5 6 5 6 5 2 2 2 2 4 4 4 4 1 1 1 1 3 3 3 3 8 4 4 4 4 7 7 (8) (7) (6) (5) 5 6 5 6 5 6 5 2 2 2 2 4 4 4 4 1 1 1 1 3 3 3 3 8 4 4 4 4 7 7 (8’) (7’) (6’) (5’) 5 6 5 6 5 6 2 2 2 4 4 4 1 1 1 3 3 3 8 8 8 4 4 4 7 7 7 9 9 9 (9) (9’) (9”) Figure 2.2: A step-by-step illustration of the decomposition T into pseudo-trapezoids and of the polyg- onalization of the union. See Section 2.2.4. An animation of this figure is available online at http://sarielhp.org/blog/?p=8920; see also Figure 4.2. 9 intersection points at depths 0 or 1 (including leftmost and rightmost points of disks), for some suitable absolute constant c. Clearly, these considerations also apply to any subset of D. This allows us to order the members of D as D ,...,D , so that the following property holds. Set 1 m D := {D ,...,D }, for i = 1,...,m. Then D contains at most c intersection points at depths 0 and 1 i 1 i i of A(D ). Equivalently, for each i, the boundary of D0 := D \U(D ) contains at most c intersection i i i i 1 − points. To prepare for the algorithmic implementation of the construction in this proof, which will be pre- sented later, we note that this ordering is not easy to obtain efficiently in a deterministic manner. Nevertheless, a random insertion order (almost) satisfies the above property: As we will show, the ex- pected sum of the complexities of the regions D0, for a random insertion order, is O(m). See later for i more details. (cid:83) We thus have U(D ) = D0 (as an openly disjoint union), for each j; for the convenience of j i j i presentation (and for the algor≤ithm to follow), we interpret this ordering as an incremental process, where the pseudo-disks of D are inserted, one after the other, in the order D ,...,D , and we maintain 1 m the partial unions U(D ), after each insertion, by the formula U(D ) = U(D )∪D0. j j j 1 j − 2.2.2. Decomposing the union into vertical trapezoids. Since the boundary of D0 = D \U(D ) i i i 1 contains at most c intersection points, we can decompose D0 into O(1) vertical pseudo-trapezoids, us−ing i the standard vertical decomposition technique; see, e.g., [SA95]. Let T be the collection of pseudo- j trapezoids in the decomposition of U(D ), collected from the decompositions of the regions D0, for j i i = 1,...,j, and let V be the set of vertices of these pseudo-trapezoids, each of which is either an j intersection point (more precisely, a boundary intersection or an x-extreme point) of A(D ), or an j intersection between some ∂D and a vertical segment erected from an intersection point of A(D ). i j Each of the pseudo-trapezoids in T is bounded by (at most) two vertical segments, a portion of j the boundary of a single pseudo-disk as its top edge, and a portion of the boundary of (another) single pseudo-disk as its bottom edge; see Figure 2.2. We have D0 = D , which we regard as a single 1 1 pseudo-trapezoid, in which the vertical sides degenerate to the leftmost and rightmost points of ∂D ; see 1 Figure 2.2(1). Note that in the vertical decomposition of D0 we split it by vertical segments through the i intersection points on its boundary, but not through vertices of V on ∂D0 which are not intersection i 1 i − points of A(D). (Informally, these vertices are “internal” to U(D ), and are not “visible” from the i 1 − outside.) See, e.g., Figure 2.2(4). The set V is obtained by adding to V the vertices of the pseudo- i i 1 trapezoids in the decomposition of D0. − i IfD0 isboundedtheneachpseudo-trapezoidτ initsdecompositionhasatopboundaryandabottom i boundary, but one or both of the vertical sides may be missing (see, e.g., Figure 2.2(1) for the single pseudo-trapezoid D0 = D and Figure 2.2(3) for the left pseudo-trapezoid of 3). From the point of view 1 1 of τ, each of the top and bottom boundaries of τ may be either convex (if it is a subarc of ∂D on ∂D0), i i or concave (if it is part of the boundary of some previously inserted pseudo-disk); If D0 is not bounded i then some of the vertical pseudo-trapezoids covering D0 will also be unbounded and missing some of i their boundaries. Note that D0 is not necessarily connected; in case it is not connected we separately i decompose each of its connected components into vertical pseudo-trapezoids in the above manner; see Figure 2.2(4). At the end of the incremental process, after inserting all the m pseudo-disks in D, the pseudo- trapezoids in T := T cover U(D), which may or may not be the entire plane, and they are pairwise m openly disjoint. By construction, each pseudo-trapezoid in T is contained in a single pseudo-disk of D. Moreover, since the complexity of each D0 is O(1), the total number of pseudo-trapezoids in T is O(m). i So T possesses some of the properties that we want, but it is not a triangulation. 10