Combinatorial complexity of signed discs

Diane L. Souvaine, Chee Keng Yap

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Let C+ and C be two collections of topological discs of arbitrary radii. The collection of discs is ‘topological’ in the sense that their boundaries are Jordan curves and each pair of Jordan curves intersect at most twice. We prove that the region ∪C+−∪C has combinatorial complexity at most 10n-30 where p=|C+|, q=|C| and n=p + q ≥ 5. Moreover, this bound is achievable. We also show bounds that are stated as functions of p and q. These are less precise.

Original languageEnglish (US)
Title of host publicationAlgorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings
EditorsFrank Dehne, Jorg-Rudiger Sack, Nicola Santoro, Sue Whitesides
PublisherSpringer Verlag
Number of pages12
ISBN (Print)9783540571551
StatePublished - 1993
Event3rd Workshop on Algorithms and Data Structures, WADS 1993 - Montreal, Canada
Duration: Aug 11 1993Aug 13 1993

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume709 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other3rd Workshop on Algorithms and Data Structures, WADS 1993

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Combinatorial complexity of signed discs'. Together they form a unique fingerprint.

Cite this