Math @ Duke

Publications [#235409] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Aronov, B; Chan, TM; Sharir, M, On levels in arrangements of lines, segments, planes, and triangles,
Discrete & Computational Geometry, vol. 19 no. 3
(1998),
pp. 315331, ISSN 01795376
(last updated on 2017/12/11)
Abstract: 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 wellknown kset 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 ksets 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 3space is O(n2k5/6α(n/k)).


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

