Combinatorial complexity of signed discs

Diane L. Souvaine; Chee Keng Yap

doi:10.1007/3-540-57155-8_281

Combinatorial complexity of signed discs

Diane L. Souvaine, Chee Keng Yap

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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	https://doi.org/10.1007/3-540-57155-8_281
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/Territory	Canada
City	Montreal
Period	8/11/93 → 8/13/93

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/3-540-57155-8_281

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

Combinatorial complexity of signed discs. / Souvaine, Diane L.; Yap, Chee Keng.

Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings. ed. / Frank Dehne; Jorg-Rudiger Sack; Nicola Santoro; Sue Whitesides. Springer Verlag, 1993. p. 577-588 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 709 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Souvaine, DL & Yap, CK 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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 709 LNCS, Springer Verlag, pp. 577-588, 3rd Workshop on Algorithms and Data Structures, WADS 1993, Montreal, Canada, 8/11/93. https://doi.org/10.1007/3-540-57155-8_281

Souvaine DL, Yap CK. Combinatorial complexity of signed discs. In Dehne F, Sack J-R, Santoro N, Whitesides S, editors, Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings. Springer Verlag. 1993. p. 577-588. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/3-540-57155-8_281

Souvaine, Diane L. ; Yap, Chee Keng. / Combinatorial complexity of signed discs. Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings. editor / Frank Dehne ; Jorg-Rudiger Sack ; Nicola Santoro ; Sue Whitesides. Springer Verlag, 1993. pp. 577-588 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{63b36ca7b4ca46c9a1261cc21db4068d,

title = "Combinatorial complexity of signed discs",

abstract = "Let C+ and C− be two collections of topological discs of arbitrary radii. The collection of discs is {\textquoteleft}topological{\textquoteright} 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.",

author = "Souvaine, {Diane L.} and Yap, {Chee Keng}",

note = "Funding Information: *This work originated at the ParallelA lgorithms and ComputationalG eometryWorkshop (1991)a t McGin University'Bs ellairsR esearcCh entera ndw ass upporteidn part by NSF grants~ DCR-84-01898, #CCR-87-0345~8,C CR-88-0354a9n d~ CCR-91-04732. IDept. of ComputeSr cienceR, utgersU niversityN,e wB runswickN, ewJ ersey0 8903d, lsOcs.rutgers.edu. IDept. of ComputeSr cienceN, ewY ork UniversityN,e wY ork,N ewY ork 10012y, ap@cs.nyu.edu.; 3rd Workshop on Algorithms and Data Structures, WADS 1993 ; Conference date: 11-08-1993 Through 13-08-1993",

year = "1993",

doi = "10.1007/3-540-57155-8_281",

language = "English (US)",

isbn = "9783540571551",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "577--588",

editor = "Frank Dehne and Jorg-Rudiger Sack and Nicola Santoro and Sue Whitesides",

booktitle = "Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings",

}

TY - GEN

T1 - Combinatorial complexity of signed discs

AU - Souvaine, Diane L.

AU - Yap, Chee Keng

N1 - Funding Information: *This work originated at the ParallelA lgorithms and ComputationalG eometryWorkshop (1991)a t McGin University'Bs ellairsR esearcCh entera ndw ass upporteidn part by NSF grants~ DCR-84-01898, #CCR-87-0345~8,C CR-88-0354a9n d~ CCR-91-04732. IDept. of ComputeSr cienceR, utgersU niversityN,e wB runswickN, ewJ ersey0 8903d, lsOcs.rutgers.edu. IDept. of ComputeSr cienceN, ewY ork UniversityN,e wY ork,N ewY ork 10012y, ap@cs.nyu.edu.

PY - 1993

Y1 - 1993

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85029470840&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85029470840&partnerID=8YFLogxK

U2 - 10.1007/3-540-57155-8_281

DO - 10.1007/3-540-57155-8_281

M3 - Conference contribution

AN - SCOPUS:85029470840

SN - 9783540571551

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

SP - 577

EP - 588

BT - Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings

A2 - Dehne, Frank

A2 - Sack, Jorg-Rudiger

A2 - Santoro, Nicola

A2 - Whitesides, Sue

PB - Springer Verlag

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

Y2 - 11 August 1993 through 13 August 1993

ER -

Combinatorial complexity of signed discs

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this