×

On levels in arrangements of lines, segments, planes, and triangles. (English) Zbl 0899.68106

Summary: We consider the problem of bounding the complexity of the \(k\)th 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(nk^{5/3})\), on the complexity of the \(k\)th level in an arrangement of \(n\) planes in \(\mathbb{R}^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 \(k\)th level in an arrangement of \(n\) line segments in the plane is \(O(n \sqrt k\alpha (n/k))\), and that the complexity of the \(k\)th level in an arrangement of \(n\) triangles in 3-space is \(O(n^2k^{5/6} \alpha (n/k))\).

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI