THE UNION OF MOVING POLYGONAL PSEUDODISCS - COMBINATORIAL BOUNDS AND APPLICATIONS

Let P be a set of polygonal pseudodiscs in the plane with n edges in t otal translating with fixed velocities in fixed directions. We prove t hat the maximum number of combinatorial changes in the union of the ps eudodiscs in P is Theta(n(2)alpha(n)). In general, if the pseudodiscs move along curved trajectories, then the maximum number of changes in the union is Theta (n lambda(s+2)(n)), where s is the maximum number o f times any triple of polygon edges meet in a common point. We apply t his result to prove that the complexity of the space of Lines missing a set of n convex homothetic polytopes of constant complexity in 3-spa ce is O(n(2)lambda(4)(n)). This bound is almost tight in the worst cas e. (C) 1998 Elsevier Science B.V. All rights reserved.