Output-Sensitive Construction of the Union of Triangles
Eti Ezra Micha Sharir

Abstract
We present an efficient algorithm for the following problem: Given a collection T = {1 , . . . , n } of n triangles in the plane, such that there exists a subset S  T (unknown to Ë Ë us), of  n triangles, such that S  = T , construct efficiently the union of the triangles in T . We show that this problem can b e solved in sub quadratic time. In our solution, we use the approximate DisjointCover (DC) algorithm, presented as a heuristics in [9]. We present a detailed implementation of this method, which combines a variety of techniques related to range-searching in two dimensions. We provide a rigorous analysis of its p erformance in the ab ove setting, showing that it does indeed run in sub quadratic time (for a reasonable range of  ).

1

Intro duction

Many problems in computational geometry involve the task of constructing the boundary of the union of n geometric ob jects in the plane. Problems of this kind include motion planning [14], where we wish to construct the forbidden portions of the configuration space; hidden surface removal for visibility problems in three dimensions [16]; finding the minimal Hausdorff distance between two sets of points (or of segments) in IR2 [12]; applications in geographic information systems [8], and many others. In this paper, we focus mainly on the problem of constructing the union of n triangles in IR2 , and discuss the extension of our algorithm to other geometric ob jects in Section 4. Computing the union by constructing the full arrangement of the n input triangles, requires (n2 ) time in the worst case, which, in most cases, is wasteful, since the combinatorial complexity of the union boundary might be considerably smaller. Nevertheless, it is strongly believed that an algorithm for this problem
 Work on this pap er has b een supp orted by NSF Grants CCR97-32101 and CCR-00-98246, by a grant from the U.S.-Israeli Binational Science Foundation, by a grant from the Israel Science Fund, Israeli Academy of Sciences, for a Center of Excellence in Geometric Computing at Tel Aviv University, and by the Hermann Minkowski­MINERVA Center for Geometry at Tel Aviv University.  Scho ol of Computer Science, Tel Aviv University.  Scho ol of Computer Science, Tel Aviv University.

that runs in subquadratic time when the boundary of the union has subquadratic complexity1 is unlikely to exist, since this problem belongs to the family of 3SUMhard problems [11], which are problems that are very likely to require (n2 ) time in the worst case. See below for more details. However, subquadratic algorithms exist in several special cases, such as the case of fat triangles (namely, every angle of each triangle is at least some constant positive angle), or of triangles that arise in the union of Minkowski sums of a fixed convex polygon with a set of pairwise disjoint convex polygons (which is the problem one faces in translational motion planning of a convex polygon). In these cases, the union has only linear or near-linear complexity [13, 15], and more efficient algorithms, based on either deterministic divide-andconquer, or on randomized incremental construction, can be devised, and are presented in the above-cited papers. If the input consists of general triangles, then one can employ the randomized incremental construction (RIC) of Agarwal and Har-Peled [3], whose analysis is based on Mulmuley's theta series [16]. As discussed in [9], the above algorithm has good performance, provided that the depth d(v ) of most of the vertices v (i.e., the number of input triangles containing v in their interior) in the arrangement induced by the n input triangles, is large enough. We refer to such vertices as being deep. Otherwise, when most of the vertices in the arrangement are shal low (but of positive depth), the RIC algorithm performs poorly. In this case, one can employ the Disjoint Cover (DC) algorithm, proposed in [9] and reviewed in more details below, which has goo d performance in practice. However, from a theoretical point of view (and in view of certain pathological examples, presented in [9]), the DC algorithm can produce (n2 ) vertices of the arrangement, even if the size of the output (i.e., the number of vertices on the boundary of the union) is only linear or constant, and it can be beaten by the RIC algorithm in such cases.

is one variant of output sensitivity that one may wish to attain. In this paper we use a different notion of output sensitivity, described later in the introduction.

1 This

Copyright © 2004 by the Association for Computing Machinery, Inc. and the Society for industrial and Applied Mathematics. All Rights reserved. Printed in The United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Association for Computing Machinery, 1515 Broadway, New York, NY 10036 and the Society for Industrial and Applied Mathematics, 3600 University City Science Center, Philadelphia, PA 19104-2688

420


t1

t2

(a)

t1 t6 t5 t2

t3

t4

(b )

Figure 1: (a) An arrangement of six triangles, illustrating the first measure of output sensitivity. The triangles t1 and t2 cover the entire union, so the output size is 2. (b) Illustrating the second measure of output sensitivity. The union boundary is determined only by the triangles t1 , . . . , t4 , even though the triangles t5 and t6 cover the i hole created by 4 ti . The output size is 4 according to the second measure, and 6 according to the first one.

Output sensitivity. In this paper we derive an efficient (subquadratic) algorithm that computes the union in an "output-sensitive" manner. There are two obvious ways to define output sensitivity. The first is to measure the output size in terms of the size of  th smallest subset S  T that satisfies e S  = , and the second measure is in terms of the T  size f the smallest subset S such that  o T    . See Figure 1 for an illustration of the two S  measures. Note that if the output size is  , according to either of the two measures, the actual complexity of the union may be as large as ( 2 ) (but not larger). The second measure of output size is likely to be too weak. Indeed, consider the reduction, as presented in [11], of an instance of 3-SUM to an instance of the problem of determining whether the union of a given set of triangles fully covers the unit square. In the above reduction, let A denote an algorithm that efficiently computes the union of n triangles in the plane, in terms of the second measure, and let TA (n,  ) denote its running time, expressed as a function of the total number n of input triangles and of the output size  . We

suppose that TA (n,  ) = o(n2 ) when  = o(n). In order to determine efficiently whether the given triangles fully cover the unit square, we consider only the portions of the triangles that are contained in the unit square, and triangulate them. In addition, we add four thin and narrow triangles that cover the boundary of the unit square. We now run A on the newly constructed instance. Clearly, there are no holes in the union of the newly created triangles if and only if the original union contains the unit square. In this case the boundary of the new union consists of only four triangles, and thus A will terminate in a predictable subquadratic time. We thus run A. If it terminates within the anticipated (subquadratic) time, we can determine at no extra cost, whether the union covers the unit square. Otherwise, we stop A, and correctly report that the union of the original triangles does not cover the unit square. Hence an efficient output-sensitive solution, under the second measure, would have yielded a subquadratic solution to 3-SUM, and is thus unlikely to exist. In contrast, the first measure does lend itself to an efficient output-sensitive solution, which is the main result of this paper. Our results. Specifically, we present an efficient algorithm to construct the boundary of the union of a set T = {1 , . . . , n } of n triangles in the plane, under the assumption that there exists a subset S  T of    n triangles (unknown to us) such that S  = . We present an efficient subquadratic algoT rithm for computing the union in this special case, whose precise performance bound is given in Theorem 2.1 (and is subquadratic for a reasonable range of the parameter  ; see below). Our approach is a randomized algorithm, based on the approximate DC algorithm, presented as a heuristics in [9]. We present a detailed (randomized) implementation of this metho d, in which we employ a technique for efficiently counting and reporting all red-blue intersections between a set of red line-segments and a set of blue line-segments [1], as well as standard techniques for range-searching in two dimensions [5, 7]. We provide a rigorous analysis of the algorithm performance in the above setting, showing that it does indeed run in (expected) subquadratic time. In particular, we first derive a subquadratic bound on the expected number of vertices generated by our version of the DC algorithm. Then we present a detailed implementation of the algorithm, which results in an overall subquadratic solution. We note that, when measuring the expected number of vertices generated by the algorithm, it suffices (and is appropriate) to consider only vertices at positive depth, since vertices at depth 0 are the vertices of the union, and they have to be constructed by any algorithm that computes the

421


union. We call the latter quantity, namely the number of positive-depth vertices generated by the algorithm, the residual cost of the approximate DC algorithm (or of any alternative algorithm). In Section 2 we briefly present the approximate DC algorithm, and derive an upper bound on its expected residual cost. Section 3 describes a detailed implementation of the approximate DC algorithm. We give concluding remarks and suggestions for further research in Section 4. 2 The Approximate Disjoint Cover Algorithm

The approximate DC algorithm is described in detail in [9]. For the sake of completeness, we recall briefly some of these details. The algorithm is incremental, and adds the triangles one at a time, maintaining the union after each insertion (in this paper we use a slightly different implementation). The insertion order of the triangles is computed as follows. We denote by V + the set of vertices of the arrangement A(T ) at positive depth (considering only intersection points of the triangle boundaries and ignoring triangle vertices), and let R  V + denote a random subset of V + . Suppose we have already inserted (1 , . . . , j -1 ). We regard each triangle as an open set. For each of the remaining triangles , we set (temporarily) S to be the set of all vertices of R in (the interior of )  that are i not covered by <j i . We compute the corresponding weights Wj () = |S | of all the remaining triangles , and set j to be the triangle with the maximum weight2 . We proceed in this manner until all triangles have been chosen. As discussed in [9], when R = V + , we get the DC algorithm in its "ideal setting", that is, every triangle gets its actual weight. However, using the entire set V + as R is much too much to ask for: Besides being too expensive (in the worst case), having V + at hand allows one to finish the computation of the union at very little extra cost. Thus, we take R to be a smaller subset of r elements, constructed by randomly selecting r vertices out of V + . We postpone the description of the actual computation of R to Section 3, and proceed for the time being under the assumption that we have managed to sample such a subset R. At the j -th iteration, we associate with each triangle  two estimators: the first, denoted by Nj (), is the actual number of vertices of A(T ) (that is, of iV + ) in (the interior of )  that are not covered by <j i ; the second is its (temp orary) weight Wj ().
2 This is somewhat different from the variant of the technique 1 in [9], where each vertex V is assigned a weight of d(v) and Wj () is the sum of weights of the vertices in S .

We show that the approximate DC algorithm chooses at the j -th iteration a triangle , whose real weight Nj () does not differ significantly from the largest real weight of a triangle at this step. As shown in Theorem 2.1, this suffices to conclude that the residual cost of the DC algorithm is subquadratic for the case under consideration (involving small output size). Intuitively, in order to guarantee a good approximation to the actual weights of the triangles, the subset R has to be large enough. However, R cannot be to o large, since then it would slow down the performance of the algorithm. An appropriate choice of the size of R is specified in what follows. The following lemma provides a lower bound for the size of R, needed to guarantee a good approximation for all triangles with large (temporary) weights. The case of triangles with smaller weights is analyzed in Lemma 2.2. (Note that both lemmas do noassume that there exists t  a subset S  T such that S  = T . This assumption is realized only in Theorem 2.1.) In what follows, we say that an event occurs with overwhelming probability (or w.o.p., for short), if the 1 probability that it does not occur is at most nc , for some constant c  1. Lemma 2.1. Let T = {1 , . . . , n } be a given col lection of n triangles in the plane, let V + denote the set of vertices of the arrangement A(T ) at positive depth, let  denote the size of V + , and let  < n denote a fixed parameter. Let R be a random sample of r = ( tlog n) positive-depth vertices, for some parameter t and with a sufficiently large constant of proportionality. Then, w.o.p., for every triangle , satisfying Nj () = ( t ),  we have r  W r c Nj () log n, () - Nj () j   provided that c is a sufficiently large constant. Pro of: For simplicity of exposition, we present the analysis under the model where R is obtained by drawing each point of V + independently with probability r p =  . Nevertheless, the assertion of the lemma holds also for other models of sampling R, including the mo del we use in the actual implementation of the algorithm, a detailed description of which is given in the full version of this paper. Note that some of the points of R i may be contained in (the interior of ) <j i . Neveri theless, since each point in V + \ <j i is chosen with r probability  , the expected (temporary) weight of each r triangle  is  Nj (). Clearly, Wj () is a random variable, representing the temporary weight of  in the j -th iteration of

422


whenever  satisfies Nj () = ( t ).  Using a large deviation bound given in [6, Theorems We next note that Inequality (2.1) is too weak when A.11 and A.13], and the fact that the expectation of a is larger than pNj (). In fact, a better bound follows r Wj () is  Nj (), it follows that from [6, Corollary A.10]: > < W < W r r r a (2.1) Pr j () - Nj () (2.3) Pr () - Nj () >  Nj () j    2e 2pNj ()
-a2

the DC algorithm, which can be viewed as the sum 0 <  < 1, which can be made arbitrarily small (for a of Nj () mutually independent indicator variables, proper choice of c) such that, w.o.p., X1 , . . . , XNj () , each satisfying (1 - )r (2.2) Wj ()  Nj (),  P r[Xi = 1] = p; P r[Xi = 0] = 1-p, for i = 1, . . . , Nj ().

+ 2(pNa ())2
j

3

,

e-  Nj ()[( +1) ln( +1)- ] . Using this bound, we obtain Lemma 2.2. Let T , V + , ,  and r be as in Lemma 2.1. Let j -1 denote the number of positive-depth vertices that have not been covered by the first j - 1 triangles chosen by the DC algorithm, and assume that j -1   . t Then, w.o.p., each remaining triangle  satisfies
(2.4) Nj ()  min

r

r for any a > 0. Substituting a = c  Nj () log n, we obtain r < W > r c Nj () log n Pr () - Nj () j  
-c
2 log n 2

1

2e

c -  r log n 



.
Nj ()

( 1 -  )


j -1

,

 j -1 Wj () -  · r 

,

In other words, the above is the probability that the temporary weight of , set by the approximate DC algorithm, differs from its expected value E(Wj ()) E (Wj ()) log n. The probability that by more than c there exists at least one such triangle is at most r < W >  r c Nj () log n Pr j () - Nj ()  
T -c
2 log n 2

for any fixed 0 <  < 1, provided that the constants of proportionality are sufficiently large. Pro of: Fix a weight W0 , and, for each remaining triangle   T , consider the event A : Substituting = Wj () - r Nj () > W0 . 

1

j 2 ne , 4 in (2.3), we obtain If r  max c2 Nj) log n then the above proba(  +1 2 P r[A ] < e-W0 [  ln( +1)-1] . bility is at most 2n1-c /4 . Hence the complementary event occurs w.o.p. when c  3, say. Hence, if we As is easily verified, the function choose r = (t log n), the above inequality holds for  +1 every triangle  that satisfies Nj () = ( t ) (with the  ln( + 1) - 1, f ( ) = constant of proportionality linear in the constant in the  choice of r). This completes the proof of the lemma. 2 Lemma 2.1 implies that if we are left with at least defined for  > 0, is monotone increasing and tends to one heavy triangle (i.e., a triangle whose temporary 0 as  tends to 0. If, for some fixed 0 <  < 1, weight is at least ( t )) in the j -th iteration, then, (1 -  )W0  , Nj () < w.o.p., each such heavy triangle  satisfies r r r then  >  /(1 -  ), implying that Nj () log n, Wj ()  Nj () - c   1 1 (2.5) P r[A ] < e-W0 [  ln 1- -1] , for a sufficiently large constant c. r r Since  Nj () log n  Nj () (by the choice of where the expression in the brackets in the exp onent is r and the assumption on Nj ()), there is a constant positive.

c -  r log n



.
N ()

W0 rNj ()

423


We keep iterating in this manner. At the j -th step, we are left with a subset Vj -1 of positive-depth vertices, so assume that Nj () < of size r- W0 =   j 1 , (2.5) implies that the probability that j -1 i  j -1 =  - Ni (i ), (2.4) does not hold for  is at most Clearly, if Nj ()  which are not covered by any of the first j - 1 triangles. If j -1 is smaller than /t, we stop this part of the Since we have assumed that j -1   , it follows, using algorithm. Otherwise, the remaining triangles of S still t the fact that r = (t log n), that the above probability cover all the remaining positive-depth vertices, and the is at most 1/nc, for an appropriate constant c (that number of these triangles can only decrease. Hence, also depends on  ). Hence, the probability that at least there exists a remaining triangle  of S that covers at one triangle  violates (2.4) is at most 1/nc-1. Hence, least j -1 / remaining positive-depth vertices. Since w.o.p., (2.4) holds for all triangles . 2 this number is ( t ), Lemma 2.1 can be applied. Using  Remark: Both Lemmas 2.1 and 2.2 rely on the a new sample R(j ) of r vertices of V + , we thus obtain (implicit) assumption that the choice of 1 , . . . , j -1 that, w.o.p., is independent of the choice of R. In particular, for the (1 - )r j -1 lemmas to be applicable at each stage of the iteration, R · , Wj ()    should be redrawn from scratch at each iteration. (See below for a discussion of this issue.) (with respect to R(j ) ), and so the chosen triangle j also We now have: satisfies this inequality. As above, using (2.4), w.o.p., Theorem 2.1. Let T = {1 , . . . , n } be a given col lec- either (1 -  )j -1 , Nj (j )  tion of n triangles in the plane, and assume that there  exists a subset S  T of   n triangles (unknown to  or + us) such that S  = T . Let V ,  and t be  r  j -1 r · , Wj (j ) - Nj (j )  as above. Then one can implement the approximate DC    algorithm, so that its residual cost is O( 2 log2 t +  ), t  w.o.p. In particular, for t = 2 , the residual cost is This implies that, in either case we have O( 2 log2 n). (1 -  -  )j -1 . (2.7) Nj (j )   Pro of: We set V0 = V + and  = |V0 |. We use the same notation as above for r, Nj () and Wj (), and assume Thus, using induction on j , the number of remaining positive-depth vertices j satisfies that r = (t log n), for the given parameter t. j 1 Since there exists a subset S  T of  n triangles  1-- whose union is equal to . j   - T , the triangles in S cover (2.8)  all the vertices in V + , and thus also all the vertices in R. Thus there exists a triangle in S that contains at Let q denote the number of triangles chosen at least r/ vertices of R (in its interior). It follows that this part of the algorithm. In particular, we have the first triangle 1 chosen by the DC algorithm (which q-1   > q . Note that after inserting all triangles t is not necessarily an element of S ), also satisfies of S , the partial union is equal to the overall union, and e hence the actual weights of the remaining triangles are all 0. However, some of the triangles of S may remain unchosen after the first q iterations. In either case, (2.8) Using (2.4) and noting that 0 = , we conclude implies q -1 1 that, w.o.p., either N1 (1 )  (1 -  )  , or W1 (1 ) -  1--  r r    q -1   -  N1 (1 )   . Hence, in either case we have t  r W1 (1 )  .  (2.6)  N1 (1 )  (1 -  ) .  (  )  e-(q-1)
1--  r - j -1 

(1- )j-1 then (2.4) holds,  (1- )j-1 . Then, putting 

=1

1 [ln 1- - ] .

,

In other words, 1 covers of the arrangement A(T ).

 and it therefore follows that q  1 + 1-- ln t, that is, positive-depth vertices the number of triangles chosen in the first part of the DC algorithm is O( log t).

424


After having chosen the first q triangles, we insert the other triangles in an arbitrary order. As a matter of fact, we may add all of them in a single step. The first q triangles that the DC algorithm inserts can generate, among themselves, at most O(q 2 ) vertices. In addition, the number of vertices of V + that have not been covered by the first q inserted triangles is, by construction, at most /t. As the algorithm inserts the remaining triangles, it may, in the worst case, generate all the   remaining positive-depth vertices, and we t make no attempt to optimize its performance from this point on. It follows that, w.o.p., the overall residual cost of the DC algorithm is bounded by   O(q 2 ) + = O( 2 log2 t) + . t t This completes the proof of the theorem. 2 Discussion. Clearly, if our only concern is to have the algorithm generate as few positive-depth vertices as possible3 , we should choose t as large as possible. For  example, as noted, if we choose t = 2 , then the residual cost of the approximate DC algorithm is at most O( 2 log2 n), w.o.p. Since there are only  triangles that define the union, the combinatorial complexity of the boundary of the union is only O( 2 ). This implies that, for the above choice of t, the overall number of vertices that the DC algorithm generates is O( 2 log2 n), which is subquadratic if  n. However, if we are concerned with the actual running time, large values of t will slow down the algorithm. For example, for this choice of t, r has to be ( t log n) = (  log n).  Since we have to choose a new sample at each of the first q iterations of the algorithm, the above may cost ( log n ·  log n) = ( log2 n), which is worse than a  simple-minded sweep-based (or randomized incremental) algorithm that computes the union (and the entire arrangement, for that matter) in time O(n log n+) [16]. Hence, in the actual implementation of the algorithm, presented in Section 3 below, we will choose a smaller value for t, in order to optimize the bound on the actual running time of the algorithm. This will affect the bound on the residual cost; see below for details. We also note that the bound O(q 2 ) on the complexity of the union of the first q triangles may be too pessimistic in practice. If the complexity of the union turns out to be smaller, the residual cost will be smaller too.

the actual generation of positive-depth vertices), such as the construction of the random samples R(j ) , the preprocessing time needed to compute all (temporary) weights with respect to R, and the time required for the actual construction of the union of the input triangles. The implementation given in [9] has good performance in practice, but its worst-case performance is hard to analyze. We present here an implementation that uses a battery of sophisticated, albeit standard, tools, based on range searching and related techniques [1, 5, 7], and lead to a subquadratic output-sensitive algorithm for constructing the union. In the following description, we denote by q the number of triangles chosen in the first stage of the algorithm, which cover all but at most  positive-depth t vertices, where  and t are as in Theorem 2.1. We note that the determination of q depends on the ability to count the number of uncovered vertices, which is not an easy task to implement efficiently. Nevertheless, we show that q can be well approximated.

Sampling R. Recall that we have to draw a new subset R in each iteration of the DC algorithm, in order to eliminate any dependence between the shape of the present union and the (current) sample R. This makes the algorithm slightly more involved, and causes some degradation of its performance -- see below. The task at hand is to construct, at the j -th triangle selection step, a random sample of (an expected number of ) r positive-depth vertices of A(T ). Let E denote the set of 3n edges of the triangles in T . We apply the technique of Agarwal [1] (see also [4]) that constructs a representation of the intersection graph of E as the disjoint union of complete bipartite graphs {Ai ×Bi }s=1 , i i so that (|Ai | + |Bi |) = O(n4/3+ ), for any  > 0. The construction takes O(n4/3+ ) time. Once this decomposition is constructed, sampling i is easy: Put M = |Ai | · |Bi |. Clearly, M =  +  is the total number of vertices of A(T ), where  is  the number of vertices on the boundary of T . If  = O( ) then the entire arrangement has only O( ) = O( 2 ) vertices, and can thus be constructed in time O(n log n +  2 ), using any of the standard techniques [16]. (Note that the above construction can also be used for counting the number of vertices of A(T ).) We may thus assume that   . We sample vertices one by one. At each sampling step we draw a random number j between 1 and M . We 3 Implementation of the Algorithm find the index i such that The actual cost of the algorithm depends on the cost i i of several support routines (in addition to the cost of Mi  |Ai | · |Bi | < j  |Ai | · |Bi |,
<i i

argument is made in [9] for the practical significance of this dogma.

3 An

and pick the (j - Mi )-th edge of the graph Ai × Bi ,

425


1 , . . . , j -1 in a range searching data structure, and query with the points of R to find those that are contained in at least one of these triangles, and to remove them from R; see [1] for details. The cost of this step is O(j 2/3+ r2/3+ ), for any  > 0. We then store the remaining points of R in a similar range searching data structure, and query with each of the remaining triangles of T to count how many of the (remaining) points of R it contains. Again, the cost of this step is O(n2/3+ r2/3+ ), for any  > 0. Hence Computing the Insertion Order. As already de- the cost of a single iteration of the DC algorithm is scribed in the preceding section, at the j -th step of the O(n2/3+ r2/3+ ). Since we repeat this procedure for q approximate DC algorithm we compute, for each of the steps, the overall cost of the first stage of the algorithm remaining triangles , the (temporary) set S , which is O(q n2/3+ r2/3+ ) = O(n2/3+ r2/3+  ), for any  > 0. is the set of all vertices of R in (the interior of )  that i are not covered by <j i , and set the corresponding The Actual Construction of the Union. The imweight Wj () to be |S |. We then set j to be the plementation of the actual construction of the union triangle with the maximum weight. proceeds through two stages, following the analysis of We note that the preprocessing stage of computing Theorem 2.1. In the first stage we deal with the inserthe insertion order is the bottleneck in our algorithm. tion of the first q triangles, and in the second stage we Instead of the less efficient implementation of this step handle all the remaining triangles, which, as mentioned in [9], we use a range-searching approach, as presented in Theorem 2.1, cover at most  positive-depth vertices t in [7], where, for each triangle , we efficiently count of the arrangement A(T ). the number of vertices of R (which are not covered Finding the right value of q is non-trivial, since it by the previously chosen triangles) that it contains in requires us to count, after each iteration, the overall its interior. Thus, in our implementation, at the j -th number of positive-depth vertices that are still not iteration of the DC algorithm, we first have to exclude covered, and stop as soon as this number drops below all vertices of R that are contained in the interior of  (for the specific value of t that will be determined i t <j i , and then p erform a range-searching query shortly). It is to o exp ensive to conduct this test after on each of the remaining triangles [2]. Both steps each iteration, so instead we perform it only at the can be implemented using the same range searching iteration steps 1, 2, 4, . . . , 2h , . . .. machinery. For the first step, we store the triangles The test is performed as follows. Suppose that

according to some obvious lexicographical order. The intersection point of the two corresponding triangle edges is the next sampled vertex. Since   , the overwhelming ma jority of the sampled vertices will have positive depth. We can, for example, take R to be a set of 2r vertices sampled in this manner. With overwhelming probability, at least r of them will have positive depth. The elements of R at zero depth have no effect on the computation of the weights Wj (). Concerning the actual cost of the sampling, we first compute, as an additi onal preprocessing step, i all the "prefix sums" Mi = <i |Ai | · |Bi |, and store them in an array. The cost of this step is O(n4/3+ ), for any  > 0. Then drawing a single element of R takes O(log n) time, for a total sampling cost of O(r log n) per each iteration of the DC algorithm. Note that, although we have to resample at each iteration of the algorithm, the construction of {Ai × Bi }i has to be done only once. Note also that only the choice of the first q triangles requires resampling; The remaining n - q triangles can be inserted in an arbitrary order. As a matter of fact, in our implementation we insert all of them at once. Hence the overall sampling cost is O(n4/3+ + q r log n) = O(n4/3+ + r log2 n). Remark: As described in Lemma 2.1, at the j -th iteration, some of the i points of R may be contained in (the interior of ) <j i . Nevertheless, since we only consider triangles  with Nj () = ( t ) and  r = (t log n), the expected number of sample vertices in  will still be large enough.

t2

U

t3 t1

Figure 2: The second stage of the actual construction of the union. U denotes the union of the first q triangles, and t1 , t2 and t3 denote the remaining triangles to be inserted into the union. Only the portions of t1 , t2 and t3 that lie outside U are relevant.

426


we are at the j -th iteration. First, we construct the union of the first j triangles in O(j 2 ) time (using, e.g., randomized incremental construction). Next, we efficiently find the intersections of the boundary of each ofi the remaining triangles  with the boundary of n j i , ii order to collect all the p ortions of   lying outside j i . We denote the set of all such portions, over all the remaining triangles, by C . (See Figure 2 for an illustration). In order to find those portions efficiently, we process i the O(j 2 ) edges of the boundary of j i into a data structure supporting segment intersection queries [5]. We query in this structure with the boundary edges of all the remaining triangles. Since the number of segments of the second kind is at most 3n, we can count the overall number of intersections between the two sets of segments in time O(n2/3+ j 4/3+ ). If this number is more than  , we conclude that j < q and continue t with the first stage. If the number of intersections is   , we compute all these intersections explicitly, and t then trim the edges of the remaining triangles to their portions outside the union of the first j triangles. We then run a line sweeping procedure on theise exterior edge portions and the boundary edges of j i . We stop the process as soon as more than  positive-depth t vertices are detected, and then conclude again that j < q and continue the first stage. If, on the other hand, the sweep encounters at most  vertices, we complete t the sweep, and thereby construct the overall union of T . We summarize our algorithm in the following procedure. Pro cedure ConstructUnion(T ) 1. Construct the intersection graph of the 3n edges of the . triangles in T as the disjoint union of complete bipartite . graphs {Ai × Bi }i . 2. for j  1 to n do 3. Construct a random sample R of r vertices out of . the vertices of A(T ). 4. Exclude all the vertices of R that are contained in i . the interior of <j i . Denote the new subset by . R. 5. Efficiently count the number of vertices of R that . are contained in (the interior of ) each of the . remaining triangles. 6. Choose the next triangle (to be inserted into the . union) as the triangle with the maximum . (temporary) weight. 7. if j is a power of 2 then 8. Construct the union of the first j triangles. 9. Count the number of intersections of the boundary . of each of the remaining triangles with the i . boundary of j i . 10. if this number is more than  goto 2. t

11. el s e Compute all these intersections explicitly, and 12. . then trim the edges of the i emaining triangles r to their portions outside j i . Denote the . . set of the resulting segments by C . 13. Run a line sweeping proci dure on C and e . the boundary edges of j i . 14. if more than  vertices are detected then t 15. stop the sweep-procedure and goto 2. el s e 16. 17. the sweep-line procedure is completed and . the union of T is reported. 18. endif 19. endif 20. endif 21. endfor 22. end Recall that q = O( log n) and that we have to choose r = c t log n, for some constant c (note that r is independent of the estimated value of q ). The overall cost of the algorithm is thus n + O 4/3+ + q r log n + q n2/3+ r2/3+ + n2/3+ q 4/3+ O O n
4/3+

q

2

+

=  log n +  2 log2 n t

+ +  2 t log3 n + n2/3+  5/3+ t2/3+ = n  O 2/3+  4/3+ + log n +  2 log2 n t . n  O 4/3+ +  2 t log3 n + n2/3+  5/3+ t2/3+ + log n t Choose t 
3/5

t = max

 n2/5

,1

o obtain that this running time equals to n , O 4/3+ + n2/5+ 2/5+  1+ for any  > 0. Since  = O(n2 ) and  n, this is always upper bounded by O(n4/3+ + n6/5+  1+ ), and one can see that this running time is subquadratic for every  n4/5 . (For smaller values of , a more 3/5 refined threshold is   .) Note that the number of n2/5 positive-depth vertices generated by the DC algorithm, as was shown in Theorem 2.1, can be guaranteed to be subquadratic for any  n, with a different choice of t. However, to obtain a subquadratic bound on the running time, we have to choose the parameter t in the above manner, which yields the bound O( 2 log2 n +  2/5+ 2/5+ 1+   ) on the number of generated t ) = O(n vertices at positive depth, which is larger than the better

427


bound provided by Theorem 2.1. We note that this degradation is mainly caused by the need to resample R at each of the first q steps of the algorithm. In summary, we have shown Theorem 3.1. Let T be a set of n triangles in the plane whose arrangement has  vertices and whose union is equal to the union of a subset of  n triangles. Then the union can be constructed in randomized expected time O(n4/3+ + n2/5+ 2/5+  1+ ), for any  > 0. 4 Concluding Remarks

We have presented an output-sensitive algorithm for the problem of constructing efficiently the union of n triangles in the plane, whose running time is expressed in terms of the smallest size  of a subset of the triangles whose union is equal to the union of the entire set. We have presented a concrete implementation of the heuristic approximate DC algorithm of [9], and showed that its expected residual cost (number of generated positive-depth vertices) is subquadratic when  n. We have also presented a detailed implementation of this method, showing that the above problem can be solved in subquadratic time, when  is reasonably small ( n4/5 ). One motivation for our algorithm is that sometimes one might expect that only a small number of triangles determine the union of the entire triangle set. In such a case, even though the value of  is unknown, it is possible to run our algorithm with the values n4/5 ,  = 1, 2, 4, . . . , 2i , . . . (where i 4 5 log n). If  the algorithm will terminate in subquadratic time, and the actual value of  will be well approximated (up to a constant factor). Our solution raises several open problems. The major problem is to improve the running time of the algorithm. Recall that the preprocessing stage of choosing the first q triangles is the bottleneck of our algorithm, since we have to resample a random subset R  V + , and recompute the (temporary) weights of the remaining triangles at each iteration. Although our approach seems wasteful, we believe that a single sample R might not be always sufficient to guarantee the inequalities (2.2) References and (2.4), and, as a result, Theorem 2.1 may be violated. Note that the theory of random sampling and [1] P. K. Agarwal. Intersection and Decomposition Algoapproximations (see, e.g., [6]) is not directly applicable rithms for Planar Arrangements. Cambridge Univerto argue that Wj () is a good approximation of Nj () sity Press, New York, USA, 1991. (in particular, when choosing r as in Lemma 2.1). This [2] P. K. Agarwal and J. Erickson. Geometric range is because the portion of the plane over wi ich Nj () h searching and its relatives. In B. Chazelle, E. Goodis estimated at the j -st step, namely,  \ <j i , may man, and R. Pollack, editors, Discrete and Computanot have constant complexity (which is a (sufficient) tional Geometry: Ten Years Later. Mathematical Socondition that is usually needed to be assumed in orciety Press, 1997. der to facilitate the application of the random sampling [3] P. K. Agarwal and S. Har-Peled. Two randomized

theory). Thus, in order to guarantee a good approximation, we first have to decompose these portions into constant-size components, and then apply the theory of -approximations on each such component. However, this would require a much larger sample size, which would actually cause the algorithm to run slower. Another direction for further research is to determine whether there exist simpler efficient approaches to the problem studied in this paper. We note that the standard randomized incremental construction (RIC) of [16] may fail in this case. In fact, the standard bad example for the RIC, consisting of n triangles that form (n2 ) shallow vertices that are all covered by one large triangle (or, more generally, sparsely covered by  n triangles), shows that the RIC may fail to construct the union in an output-sensitive manner. Another challenging problem is to extend the results of this paper to the union of other planar shapes, and to unions (of, say, simplices) in three dimensions. We have extended our algorithm to the union of axisparallel ellipses in IR2 . The resulting algorithm constructs the union of n such ellipses in O(n8/5+ + 4/11+ n6/11+  1+ + n log2 n) time, for any  > 0, where  and  are as above, a bound that is slightly worse than the bound we have for the original problem, involving triangles in IR2 . Here the algorithm runs in subquadratic time when  n8/11 . We omit further details of this extension due to lack of space. When applying our algorithm to simplices in three dimensions, we first have to solve efficiently the problem of representing in a compact form all triples of intersecting simplices, in order to produce a random subset R  V + . We have designed an algorithm that counts and represents all intersecting triples in near-quadratic time an storage [10]. Using this procedure, combined with standard range searching machinery for three dimensions, we can compute the union of n simplices in IR3 in subcubic time, when the union is determined by  n simplices. Acknowledgments. The authors wish to thank Sariel Har-Peled for useful discussions on this problem.

428


[4]

[5]

[6] [7]

[8]

[9]

[10]

[11]

[12]

[13]

[14] [15]

[16]

incremental algorithms for planar arrangements, with a twist. Manuscript, 2001. P. K. Agarwal and M. Sharir. Red-blue intersection detection algorithms, with applications to motion planning and collision detection. SIAM J. Comput., 19(2):297­321, 1990. P. K. Agarwal and M. Sharir. Applications of a new space-partitioning technique. Discrete Comput. Geom., 9(1):11­38, 1993. N. Alon and J. H. Sp encer. The Probabilistic Method. Wiley-Interscience, New York, USA, 2000. B. Chazelle, M. Sharir, and E. Welzl. Quasi-optimal upp er b ounds for simplex range searching and new zone theorems. Algorithmica, 8:407­429, 1992. M. de Berg, M. Katz, A. F. van der Stapp en, and J. Vleugels. Realistic input models for geometric algorithms. In Proc. 13th Annu. ACM Sympos. Comput. Geom., pages 294­303, ACM Press, 1997. E. Ezra, D. Halp erin, and M. Sharir. Sp eeding up the incremental construction of the union of geometric ob jects in practice. In Proc. 10th European Symposium on Algorithms, pages 473­484, 2002. Also to app ear in Comput. Geom. Theory Appl. E. Ezra and M. Sharir. Counting and representing intersections among triangles in three dimensions. Manuscript, 2003. A. Ga jentaan and M. H. Overmars. On a class of O(n2 ) problems in computational geometry. Comput. Geom. Theory Appl., 5:165­185, 1995. D. P. Huttenlocher, K. Kedem, and M. Sharir. The upp er envelop e of voronoi surfaces and its applications. Discrete Comput. Geom., 9:267­291, 1993. K. Kedem, R. Livne, J. Pach, and M. Sharir. On the union of Jordan regions and collision-free translational motion amidst p olygonal obstacles. Discrete Comput. Geom., 1:59­71, 1986. J.-C. Latomb e. Robot Motion Planning. Kluwer Academic Publishers, Boston, MA 1991. J. Matouek, N. Miller, J. Pach, M. Sharir, S. Sifrony, s and E. Welzl. Fat triangles determine linearly many holes. In Proc. 32nd Annu. IEEE Sympos. Found. Comput. Sci., pages 49­58, 1991. K. Mulmuley. Computational Geometry: An Introduction through Randomized Algorithms. Prentice Hall, Englewood Cliffs, NJ, 1994.

429