The Upper Envelope of Voronoi Surfaces and Its Applications

283

• Zf 1^12з1 is bounded by the complexity of [7123» which is

of у {t, 4- f2 + t^Mmt)

We now repeat this procedure for all triples of distinct collections Jfj, JT^, JT^, and sum up the above bounds, to obtain a total running time of

0 ( mrt ( x ( mt ) log t) = 0{mta(mt) log t).

Sifting the spurious vertices from the superset of vertices of type (iii) is done in time O(mta(mt)\ogt): We have a total of 0{mt) original edges of the polyhedra and edges formed by the intersection of any two original polyhedra. The latter can all be computed in time 0(mt log t). Let e be an edge in this collection, and assume, without loss of generality, eeJf^ u Jf2. We gather all the subintervals of e which are in the union I/12 ^^^d, throughout the merge process, we gather all the subintervals of ^ in (7i2n ^ = 3,..., r; if the number of subintervals is x, then computing their union along e is done in time 0(x log x). Since the total number of subintervals on all the edges in the collection is 0(mta(mt)), we have established the time bound claimed for the sifting operation.

Hence , if T(m, t) denotes the time needed to compute the union of m convex polyhedra (sharing a common point) with a total of t faces, then we get the following recurrence:

T ( m , t) < Y. Ц — » ^ + ^ J + cmtoi(mt) log t,

1 <i<j<r \ '* /

where с is an absolute positive constant. The first term in the equation above is the time needed for computing all the pairwise unions U^J, and the second term

( . he overhead,, i. ,he Urne needed .o сошри.е all ,he (;) „iples U.„ h, ™rg.„g

the relevant pairs.

We unfold the recurrence into a tree-like structure. At the second level of the tree a collection Jf; u JT^ is subdivided into r subcollections JT!,, x = 1,..., r. r^ denotes the total number of faces of the polyhedra in jT^. Thus at the second level we have inequalities of the form

/ 2m \ ^ /4m \ 2w

Л —, f, + f J < I T -y, 4 + r; + с — (r, + tjMmt) log t

\ ^ / l<k<l<r \^ / ^

The sum of the overhead terms at the second level of the tree is therefore X с — (t, 4- tj)(x(mt)logt = с — (x(mt) log t Y. (^. + ^)

1^i<j<r ^ ^ I < i<j<r

2 ( r - l ) , , , ^

= - - - - - - - - cmtoc ( mt ) log t.