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

preprint2025arXivOpen access

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 kk simple polygons with a total of nn sides is Θ(nα(k))Θ(n α(k) ), where α(⋅)α(\cdot) is the inverse of Ackermann's function. We also give a new and simpler proof of the bound O(mλs+2(n))O \left( \sqrt{m} λ_{s+2}( n ) \right) on the total number of edges of mm faces in an arrangement of nn Jordan arcs, each pair of which intersect in at most ss points, where λs(n)λ_{s}(n) is the maximum length of a Davenport-Schinzel sequence of order ss with nn symbols. We extend this result, showing that the total number of edges of mm faces in a sparse arrangement of nn Jordan arcs is O((n+mw)λs+2(n)n)O \left( (n + \sqrt{m}\sqrt{w}) \frac{λ_{s+2}(n)}{n} \right), where ww is the total complexity of the arrangement. Several other applications and variants of the Combination Lemma are also presented.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.