The common exterior of convex polygons in the plane

We establish several combinatorial bounds on the complexity (number of vertices and edges) of the complement of the union (also known as the common exterior) of k convex polygons in the plane, with a total of n edges. We show: (1) The maximum complexity of the entire common exterior is Theta(n alpha(k) + k(2)).(2) (2) The maximum complexity of a single cell of the common exterior is Theta(n alpha(k)). (3) The complexity of m distinct cells in the common exterior is O(m(2/3)k(2/3) log(1/3)(k(2)/m) + n log k) and can be Omega(m(2/3)k(2/3) + n alpha(lc)) in the worst case. (C) 1997 Elsevier Science B.V.