On levels in arrangements of lines, segments, planes, and triangles

Published

Journal Article

We consider the problem of bounding the complexity of the kth level in an arrangement of n curves or surfaces, a problem dual to, and an extension of, the well-known k-set problem. Among other results, we prove a new bound, O(nk5/3), on the complexity of the kth level in an arrangement of n planes in ℝ3, or on the number of k-sets in a set of n points in three dimensions, and we show that the complexity of the kth level in an arrangement of n line segments in the plane is O(n-√kα(n/k)), and that the complexity of the kth level in an arrangement of n triangles in 3-space is O(n2k5/6α(n/k)).

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Aronov, B; Chan, TM; Sharir, M

Published Date

  • January 1, 1998

Published In

Volume / Issue

  • 19 / 3

Start / End Page

  • 315 - 331

International Standard Serial Number (ISSN)

  • 0179-5376

Digital Object Identifier (DOI)

  • 10.1007/PL00009348

Citation Source

  • Scopus