Math @ Duke

Publications [#235471] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Sharir, M, Pseudoline arrangements: Duality, algorithms, and applications,
Siam Journal on Computing, vol. 34 no. 3
(2005),
pp. 526552, ISSN 00975397 [doi]
(last updated on 2018/10/22)
Abstract: A finite collection of xmonotone unbounded Jordan curves in the plane is called a family of pseudolines if every pair of curves intersect in at most one point, and the two curves cross each other there. Let L be such a collection of n pseudolines, and let P be a set of m points in R 2. Extending a result of Goodman [Discrete Math., 32 (1980), pp. 2735], we define a duality transform that maps L to a set L* of points in R 2 and P to a set P* of (xmonotone) pseudolines in R 2, so that the incidence and the "abovebelow" relations between the points and the pseudolines are preserved. We present an efficient algorithm for computing the dual arrangement A(P*) under an appropriate model of computation. We also present a dynamic data structure for reporting, in O(m ε+k) time, all k points of P that lie below a query arc, which is either a circular arc or a portion of the graph of a polynomial of fixed degree. This result is needed for computing the dual arrangement for certain classes of pseudolines arising in several applications, but is also interesting in its own right. We present a few applications of our dual arrangement algorithm, such as computing incidences between points and pseudolines and computing a subset of faces in a pseudoline arrangement. Next, we present an efficient algorithm for cutting a set of circles into arcs so that every pair of arcs intersect in at most one point, i.e., the resulting arcs constitute a collection of pseudosegments. By combining this algorithm with our algorithm for computing the dual arrangement of pseudolines, we obtain efficient algorithms for several problems involving arrangements of circles or circular arcs, such as reporting or counting incidences between points and circles and computing a set of marked faces in arrangements of circles. © 2005 Society for Industrial and Applied Mathematics.


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

