Partitioning arrangements of lines II: Applications

In this paper we present efficient deterministic algorithms for various problems involving lines or segments in the plane, using the partitioning algorithm described in a companion paper [A3]. These applications include: (i) anO(m^2/3n^2/3 · log^2/3n · log^/3 (m/n)+(m+n) logn) algorithm to compute all incidences betweenm points andn lines, where is a constant <3.33; (ii) anO(m^2/3n^2/3 · log^5/3n · log^/3 (m/n)+(m+n) logn) algorithm to computem faces in an arrangement ofn lines; (iii) anO(n^4/3 log^(+2)/3n) algorithm to count the number of intersections in a set ofn segments; (iv) anO(n^4/3 log^{( + 2)/3}n) algorithm to count red-blue intersections between two sets of segments, and (v) anO(n^3/2 log^/3n) algorithm to compute spanning trees with low stabbing number for a set ofn points. We also present an algorithm that, given set ofn points in the plane, preprocesses it, in timeO(nm log^+1/2n), into a data structure of sizeO(m) forn lognmn², so that the number of points ofS lying inside a query triangle can be computed inO((n/m) log^3/2n) time.Work on this paper has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant DCR-83-20085, and by grants from the Digital Equipment Corporation and the IBM Corporation. A preliminary version of this paper appears in theProceedings of the 5th ACM Symposium on Computational Geometry, 1989, pp. 11–22.