COUNTING FACETS AND INCIDENCES

被引：16

作者：

AGARWAL, PK ^{[1
]}

ARONOV, B ^{[1
]}

机构：

[1] POLYTECH INST NEW YORK,DEPT COMP SCI,BROOKLYN,NY 11201

来源：

DISCRETE & COMPUTATIONAL GEOMETRY | 1992年 / 7卷 / 04期

关键词：

D O I：

10.1007/BF02187848

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We show that m distinct cells in an arrangement of n planes in R3 are bounded by O(m2/3n + n2) faces, which in turn yields a tight bound on the maximum number of facets bounding m cells in an arrangement of n hyperplanes in R(d), for every d greater-than-or-equal-to 3. In addition, the method is extended to obtain tight bounds on the maximum number of faces on the boundary of all nonconvex cells in an arrangement of triangles in R3. We also present a simpler proof of the O(m2/3n(d/3) + n(d-1)) bound on the number of incidences between n hyperplanes in R(d) and m vertices of their arrangement.

引用

页码：359 / 369

页数：11

共 12 条

[1] TRIANGLES IN SPACE OR BUILDING (AND ANALYZING) CASTLES IN THE AIR [J].

ARONOV, B ;

SHARIR, M .

COMBINATORICA, 1990, 10 (02) :137-173

[2]

ARONOV B, 1992, IN PRESS 8TH P ANN S

[3]

ARONOV B, 1991, 7TH P ACM S COMP GEO, P307

[4] ON THE LATTICE PROPERTY OF THE PLANE AND SOME PROBLEMS OF DIRAC, MOTZKIN AND ERDOS IN COMBINATORIAL GEOMETRY [J].

BECK, J .

COMBINATORICA, 1983, 3 (3-4) :281-297

[5] COMBINATORIAL COMPLEXITY-BOUNDS FOR ARRANGEMENTS OF CURVES AND SPHERES [J].

CLARKSON, KL ;

EDELSBRUNNER, H ;

GUIBAS, LJ ;

SHARIR, M ;

WELZL, E .

DISCRETE & COMPUTATIONAL GEOMETRY, 1990, 5 (02) :99-160

[6] THE COMPLEXITY OF CELLS IN 3-DIMENSIONAL ARRANGEMENTS [J].

EDELSBRUNNER, H ;

HAUSSLER, D .

DISCRETE MATHEMATICS, 1986, 60 :139-146

[7] ON THE MAXIMAL NUMBER OF EDGES OF MANY FACES IN AN ARRANGEMENT [J].

EDELSBRUNNER, H ;

WELZL, E .

JOURNAL OF COMBINATORIAL THEORY SERIES A, 1986, 41 (02) :159-166

[8] THE COMPLEXITY OF MANY CELLS IN ARRANGEMENTS OF PLANES AND RELATED PROBLEMS [J].

EDELSBRUNNER, H ;

GUIBAS, L ;

SHARIR, M .

DISCRETE & COMPUTATIONAL GEOMETRY, 1990, 5 (02) :197-216

[9]

Edelsbrunner H, 1987, ALGORITHMS COMBINATO

[10] THE UPPER ENVELOPE OF PIECEWISE LINEAR FUNCTIONS AND THE BOUNDARY OF A REGION ENCLOSED BY CONVEX PLATES - COMBINATORIAL ANALYSIS [J].

PACH, J ;

SHARIR, M .

DISCRETE & COMPUTATIONAL GEOMETRY, 1989, 4 (04) :291-309

← 1 2 →