Pseudo-line arrangements: Duality, algorithms, and applications
A collection L of n x-monotone unbounded Jordan curves in the plane is called a family of pseudo-lines if every pair of curves intersect in at most one point, and the two curves cross each other there. Let P be a set of m points in R2. We define a duality transform that maps L to a set L-of points in R2 and P to a set P∗of pseudo-lines in E2, so that the incidence and the "above-below" relationships between the points and pseudo-lines are preserved. We present an efficient algorithm for computing the dual arrangement A(P∗) under an appropriate model of computation. We also propose a dynamic data structure for reporting, in 0(me + fc) 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 pseudo-lines arising in our 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 pseudo-lines and computing a subset of faces in a pseudo-line 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 pseudo-segments. By combining this algorithm with our algorithm for computing the dual arrangement of pseudo-lines, we obtain efficient algorithms for a number of problems involving arrangements of circles or circular arcs, such as detecting, counting, or reporting incidences between points and circles.
Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms
Volume / Issue
Start / End Page
International Standard Book Number 10 (ISBN-10)