A deterministic algorithm for partitioning arrangements of lines and its application
Pankaj K. Agarwal · 1989
In this paper we consider the following problem: Given a set ℒ of n lines in the plane, partition the plane into Ο(r2) triangles so that no triangle intersects more than Ο(n/r) lines of ℒ. We present a deterministic algorithm for this problem with Ο(nr log n logω r) running time, where ω is a constant < 3.3. Our algorithm is faster than Matousk's recent algorithm [Ma] for large values of r. In the second part of the paper, we apply this algorithm to several problems involving lines or segments in the plane, and obtain deterministic algorithms which are faster than any previously known algorithms. For example we give an Ο(n2/3m2/3 log n logω/3 m/√n + (m + n) log n) algorithm to compute all incidences between m points and n lines. Other problems include computing many faces in an arrangement of lines or segments, counting segment intersections, red-blue intersection detection, simplex range queries and computing stabbing trees with low stabbing number.