This is the authors' abstract. We don't add key points for this paper.
A finite collection of 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 L be such a collection of n pseudo-lines, and let P be a set of m points in ². Extending a result of Goodman [Discrete Math., 32 (1980), pp. 27--35], we define a duality transform that maps L to a set L* of points in ² and P to a set P* of (x-monotone) pseudo-lines in ², so that the incidence and the "above-below" relations between the points and the pseudo-lines 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 pseudo-lines 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 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 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.
Answers are grounded in this paper and cite their sources.
No takes yet. Share an insight, caveat, or question.
Agarwal et al. (2005) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: