### Abstract

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 language | English (US) |
---|---|

Title of host publication | Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings |

Editors | Frank Dehne, Jorg-Rudiger Sack, Nicola Santoro, Sue Whitesides |

Publisher | Springer Verlag |

Pages | 577-588 |

Number of pages | 12 |

ISBN (Print) | 9783540571551 |

DOIs | |

State | Published - 1993 |

Event | 3rd Workshop on Algorithms and Data Structures, WADS 1993 - Montreal, Canada Duration: Aug 11 1993 → Aug 13 1993 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 709 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 3rd Workshop on Algorithms and Data Structures, WADS 1993 |
---|---|

Country | Canada |

City | Montreal |

Period | 8/11/93 → 8/13/93 |

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

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

## Cite this

Souvaine, D. L., & Yap, C. K. (1993). Combinatorial complexity of signed discs. In F. Dehne, J-R. Sack, N. Santoro, & S. Whitesides (Eds.),

*Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings*(pp. 577-588). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 709 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-57155-8_281