A fast planar partition algorithm, II
K. Mulmuley · Journal of the ACM · 1991
Randomized, optimal algorithms to find a partition of the plane induced by a set of algebraic segments of a bounded degree, and a set of linear chains of a bounded degree, are given. This paper also provides a new technique for clipping, called virtual clipping , whose overhead per window W depends logarithmically on the number if intersections between the borders of W and the input segments. In contrast, the overhead of the conventional clipping technique depends linearly on this number of intersections. As an application of virtual clipping, a new simple and efficient algorithm for plannar point location is given.