Constructing Many Faces in Arrangements of Lines and Segments

We present new algorithms for computing many faces in arrangements of lines and segments. Given a set S of n lines (resp., segments) and a set P of m points in the plane, the problem is to compute the faces of the arrangements of S that contain at least one point of P .

For the line case, we give a deterministic algorithm of O(m 2/3 n 2/3 log 2/3 (n/ √ m)+(m+n) log n) time. This improves the previously best deterministic algorithm [Agarwal, 1990] by a factor of log 2.22 n and improves the previously best randomized algorithm [Agarwal, Matoušek, and Schwarzkopf, 1998] by a factor of log 1/3 n in certain cases (e.g., when m = Θ(n)).

For the segment case, we present a deterministic algorithm of O(n 2/3 m 2/3 log n + τ (nα 2 (n) + n log m + m) log n) time, where τ = minlog m, log(n/ √ m) and α(n) is the inverse Ackermann function. This improves the previously best deterministic algorithm [Agarwal, 1990] by a factor of log 2.11 n and improves the previously best randomized algorithm [Agarwal, Matoušek, and Schwarzkopf, 1998] by a factor of log n in certain cases (e.g., when m = Θ(n)). We also give a randomized algorithm of O(m 2/3 K 1/3 log n + τ (nα(n) + n log m + m) log n log K) expected time, where K is the number of intersections of all segments of S.

In addition, we consider the query version of the problem, that is, preprocess S to compute the face of the arrangement of S that contains any query point. We present new results that improve the previous work for both the line and the segment cases.