Math @ Duke

Publications [#325422] of Pankaj K. Agarwal
Papers Published
 Agarwal, P; Nevo, E; Pach, J; Pinchasi, R; Pinchasi, R; Smorodinsky, S, Lenses in arrangements of pseudocircles and their applications,
Proceedings of the Annual Symposium on Computational Geometry
(January, 2002),
pp. 123132
(last updated on 2018/03/18)
Abstract: A collection of simple closed Jordan curves in the plane is called a family of pseudocircles if any two of its members intersect at most twice. A closed curve composed of two subarcs of distinct pseudocircles is said to be an empty lens if it does not intersect any other member of the family. We establish a linear upper bound on the number of empty lenses in an arrangement of n pseudocircles with the property that any two curves intersect precisely twice. Enhancing this bound in several ways, and combining it with the technique of Tamaki and Tokuyama [16], we show that any collection of n pseudocircles can be cut into O(n 3/2 (log n) O(α(s)(n)) ) arcs so that any two intersect at most once, provided that the given pseudocircles are xmonotone and admit an algebraic representation by three real parameters; here α(n) is the inverse Ackermann function, and s is a constant that depends on the algebraic degree of the representation of the pseudocircles (s = 2 for circles and parabolas). For arbitrary collections of pseudocircles, any two of which intersect twice, the number of necessary cuts reduces to O(n 4/3 ). As applications, we obtain improved bounds for the number of pointcurve incidences, the complexity of a single level, and the complexity of many faces in arrangements of circles, pairwise intersecting pseudocircles, parabolas, and families of homothetic copies of a fixed convex curve. We also obtain a variant of the GallaiSylvester theorem for arrangements of pairwise intersecting pseudocircles, and a new lower bound for the number of distinct distances among n points in the plane under any simplydefined norm or convex distance function.


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

