Topologically sweeping an arrangement (Q1122981)

Many computation geometric problems in the plane may be solved by constructing and searching planar line arrangements, see e.g. papers by \textit{B. Chazelle}, \textit{L. Guibas}, \textit{D. T. Lee} [BIT 25, 76-90 (1985; Zbl 0603.68072)] and \textit{H. Edelsbrunner}, \textit{J. O'Rourke}, \textit{R. Seidel} [SIAM J. Comput. 15, 341-363 (1986; Zbl 0603.68104)] where optimal \(0(n^ 2)\) time and space algorithms are given for constructing planar line arrangements. In many cases, however, it turns out that one actually needs not to construct the whole arrangement explicitly but rather enumerate its elements in some (partial) order. The present paper gives an algorithm to accomplish this using only 0(n) space. The method used is the generalization of the well-known sweepline paradigm called topological line sweep where the topological line may be viewed as a y-monotone curve moving from left to right not as a whole but ``stretching out'' in amoeba-like way. This leads to space or/and time improvements for a number of problems discussed in the paper. See also the paper of \textit{L. Guibas}, \textit{R. Seidel} [Discrete Comput. Geom. 2, 175-193 (1987; Zbl 0623.68043)] for another implementation of the topological sweep for overlaying planar convex maps in time linear in the \(input+output\) size.