Multicolor combination lemma

Research output: Contribution to journalArticlepeer-review

Abstract

We present an extension of the Combination Lemma of Guibas et al. (1983) that expresses the complexity of one or several faces in the overlay of many arrangements (as opposed to just two arrangements in (Guibas et al. 1989)), 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 Θ(nα(k)), where α(·) is the inverse of Ackermann's function. We also give a new and simpler proof of the bound O(√mλs+2(n)) 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 λ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((n + √m√w)λs+2(n)/n), where w is the total complexity of the arrangement. Several other related results are also obtained.

Original languageEnglish (US)
Pages (from-to)155-176
Number of pages22
JournalComputational Geometry: Theory and Applications
Volume12
Issue number3-4
DOIs
StatePublished - Apr 1999
Externally publishedYes

Keywords

  • Arrangements
  • Combination lemma

ASJC Scopus subject areas

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Multicolor combination lemma'. Together they form a unique fingerprint.

Cite this