The Complexity of One or Many Faces in the Overlay of Many Arrangements

Abstract

We present an extension of the Combination Lemma of [GSS89] that expresses the complexity of one or several faces in the overlay of many arrangements, as a function of the number of arrangements, the number of faces, and the complexities of these faces in the separate arrangements. Several applications of the new Combination Lemma are presented: We first show that the complexity of a single face in an arrangement of $k$ simple polygons with a total of $n$ sides is $\hat{I}˜(n\hat{I}\pm (k))$, where $\hat{I}\pm (\cdot )$ is the inverse of Ackermann's function. We also give a new and simpler proof of the bound $O\left(\sqrt{m}\hat{I}{»}_{s+2}(n)\right)$ on the total number of edges of $m$ faces in an arrangement of $n$ Jordan arcs, each pair of which intersect in at most $s$ points, where $\hat{I}{»}_s(n)$ is the maximum length of a Davenport-Schinzel sequence of order $s$ with $n$ symbols. We extend this result, showing that the total number of edges of $m$ faces in a sparse arrangement of $n$ Jordan arcs is $O\left((n+\sqrt{m}\sqrt{w})\frac{\hat{I}{»}_{s+2}(n)}{n}\right)$, where $w$ is the total complexity of the arrangement. Several other applications and variants of the Combination Lemma are also presented.

Article based on MS Thesis