The common exterior of convex polygons in the plane
Boris S. Aronov, Micha Sharir · Computational Geometry · 1997
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 Θ(nα(k) + k2). 2 (2) The maximum complexity of a single cell of the common exterior is Θ(nα(k)). (3) The complexity of m distinct cells in the common exterior is O(m23k23log13(k2m) + nlogk) and can be Ω(m23k23 + nα(k)) in the worst case.