Math @ Duke

Publications [#235588] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Aronov, B; Sharir, M, On levels in arrangements of lines, segments, planes, and triangles,
in Thirteenth Annual Symposium on Computational Geometry,
Proceedings of the Annual Symposium on Computational Geometry
(1997),
pp. 3038
(last updated on 2018/10/21)
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 extending, the wellknown kset problem. (a) We review and simplify some old proofs in new disguise and give new proofs of the bound O(n√k+1) for the complexity of the kth level in an arrangement of n lines. (b) We derive an improved version of Lovasz Lemma in any dimension, and use it to prove a new bound, O(n2k2/3), on the complexity of the kth level in an arrangement of n planes in R3, or on the number of ksets in a set of n points in three dimensions. (c) We show that the complexity of any single level in an arrangement of n line segments in the plane is O(n3/2), and that the complexity of any single level in an arrangement of n triangles in 3space is O(n17/6).


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

