COMBINATORIAL COMPLEXITY OF SIGNED DISCS

被引：0

作者：

SOUVAINE, DL

YAP, CK

机构：

[1] RUTGERS STATE UNIV,DEPT COMP SCI,NEW BRUNSWICK,NJ 08903

[2] NYU,COURANT INST MATH SCI,NEW YORK,NY 10012

来源：

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 1995年 / 5卷 / 04期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1016/0925-7721(94)00026-X

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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 U C+ - U C- has combinatorial complexity at most 10n - 30 where p = \C+\, q = \C-\ and n = p + q greater than or equal to 5. Moreover, this bound is achievable. We also show less precise bounds that are stated as functions of p and q.

引用

页码：207 / 223

页数：17

共 50 条

[41] On the computational complexity of combinatorial flexibility problems
Leoni, V. A.
Nasini, G. L.
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2010, 87 (15) : 3330 - 3343
[42] The Combinatorial and Topological Complexity of a Single Cell
Discrete & Computational Geometry, 2002, 29 : 41 - 59
[43] Optimizing the topological and combinatorial complexity of isosurfaces
Andújar, C
Brunet, P
Chica, A
Navazo, I
Rossignac, J
Vinacua, A
COMPUTER-AIDED DESIGN, 2005, 37 (08) : 847 - 857
[44] On nonnegative signed domination in graphs and its Algorithmic Complexity
Huang, Z. (hzhongsheng@qq.com), 1600, Academy Publisher (08): : 365 - 372
[45] Higher analogs of simplicial and combinatorial complexity
Paul, Amit Kumar
TOPOLOGY AND ITS APPLICATIONS, 2019, 267
[46] New logical and complexity results for signed-SAT
Ansótegui, C
Manyà, F
33RD INTERNATIONAL SYMPOSIUM ON MULTIPLE-VALUED LOGIC, PROCEEDINGS, 2003, : 181 - 187
[47] COMMUNICATION COMPLEXITY AND COMBINATORIAL LATTICE THEORY
LOVASZ, L
SAKS, M
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1993, 47 (02) : 322 - 349
[48] Fast and exact signed Euclidean distance transformation with linear complexity
Cuisenaire, O.
Macq, B.
ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings, 1999, 6 : 3293 - 3296
[49] Descriptive complexity and reflective properties of combinatorial configurations
Fouche, WL
JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND SERIES, 1996, 54 : 199 - 208
[50] Time and space complexity of combinatorial auction in Telecommunication
Virant, Jernej
Kosir, Andrej
ELEKTROTEHNISKI VESTNIK-ELECTROCHEMICAL REVIEW, 2011, 78 (04): : 193 - 197

← 1 2 3 4 5 →