Constructing Many Faces in Arrangements of Lines and Segments
share
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/3n^2/3log^2/3 (n/√(m))+(m+n)log n) time. This improves the previously best deterministic algorithm [Agarwal, 1990] by a factor of log^2.22n and improves the previously best randomized algorithm [Agarwal, Matoušek, and Schwarzkopf, 1998] by a factor of log^1/3n in certain cases (e.g., when m=Θ(n)). For the segment case, we present a deterministic algorithm of O(n^2/3m^2/3log n+τ(nα^2(n)+nlog m+m)log n) time, where τ=min{log 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.11n 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/3K^1/3log n+τ(nα(n)+nlog m+m)log nlog 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.
READ FULL TEXT