Combinatorial complexity of signed discs

Diane L. Souvaine; Chee Keng Yap

doi:10.1016/0925-7721(94)00026-X

Combinatorial complexity of signed discs

Diane L. Souvaine, Chee Keng Yap

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

Let C⁺ and C^- be two collections of topological discs. 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 less precise bounds that are stated as functions of p and q.

Original language	English (US)
Pages (from-to)	207-223
Number of pages	17
Journal	Computational Geometry: Theory and Applications
Volume	5
Issue number	4
DOIs	https://doi.org/10.1016/0925-7721(94)00026-X
State	Published - Nov 1995

ASJC Scopus subject areas

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

Access to Document

10.1016/0925-7721(94)00026-X

Cite this

@article{8a68d6b0ae514c8797fcf3ad7ecd21a4,

title = "Combinatorial complexity of signed discs",

abstract = "Let C+ and C- be two collections of topological discs. 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 less precise bounds that are stated as functions of p and q.",

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

note = "Funding Information: * Corresponding author. 1 CKY is supported by NSF grants #DCR-84-01898 and #CCR-87-03458; DLS is supported by NSF grants #CCR-88-03549 and #CCR-91-04732.",

year = "1995",

month = nov,

doi = "10.1016/0925-7721(94)00026-X",

language = "English (US)",

volume = "5",

pages = "207--223",

journal = "Computational Geometry: Theory and Applications",

issn = "0925-7721",

publisher = "Elsevier",

number = "4",

}

TY - JOUR

T1 - Combinatorial complexity of signed discs

AU - Souvaine, Diane L.

AU - Yap, Chee Keng

N1 - Funding Information: * Corresponding author. 1 CKY is supported by NSF grants #DCR-84-01898 and #CCR-87-03458; DLS is supported by NSF grants #CCR-88-03549 and #CCR-91-04732.

PY - 1995/11

Y1 - 1995/11

N2 - Let C+ and C- be two collections of topological discs. 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 less precise bounds that are stated as functions of p and q.

AB - Let C+ and C- be two collections of topological discs. 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 less precise bounds that are stated as functions of p and q.

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

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

U2 - 10.1016/0925-7721(94)00026-X

DO - 10.1016/0925-7721(94)00026-X

M3 - Article

AN - SCOPUS:58149321264

SN - 0925-7721

VL - 5

SP - 207

EP - 223

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

IS - 4

ER -

Combinatorial complexity of signed discs

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this