Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke





.......................

.......................


Publications [#235588] of Pankaj K. Agarwal

Papers Published

  1. 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. 30-38
    (last updated on 2017/12/16)

    Abstract:
    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 extending, the well-known k-set 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 k-th 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 k-th level in an arrangement of n planes in R3, or on the number of k-sets 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 3-space is O(n17/6).

 

dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320