Counting facets and incidences

Journal Article (Journal Article)

We show that m distinct cells in an arrangement of n planes in ℝ are bounded by O(m n+n ) faces, which in turn yields a tight bound on the maximum number of facets bounding m cells in an arrangement of n hyperplanes in ℝ , for every d≥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 ℝ . We also present a simpler proof of the O(m n +n ) bound on the number of incidences between n hyperplanes in ℝ and m vertices of their arrangement. © 1992 Springer-Verlag New York Inc. 3 2/3 2 d 3 2/3 d/3 d-1 d

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Aronov, B

Published Date

  • December 1, 1992

Published In

Volume / Issue

  • 7 / 1

Start / End Page

  • 359 - 369

Electronic International Standard Serial Number (EISSN)

  • 1432-0444

International Standard Serial Number (ISSN)

  • 0179-5376

Digital Object Identifier (DOI)

  • 10.1007/BF02187848

Citation Source

  • Scopus