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 total translating with fixed velocities in fixed directions. We prove that the maximum number of combinatorial changes in the union of the pseudodiscs in P is T(n2a(n)). In general, if the pseudodiscs move along curved trajectories, then the maximum number of changes in the union is T(n¿s+2(n)), where s is the maximum number of times any triple of polygon edges meet in a common point. We apply this result to prove that the complexity of the space of lines missing a set of n convex homothetic polytopes of constant complexity in 3-space is O(n2¿4(n)). This bound is almost tight in the worst case.