2021/10/16 by Wang, Haitao
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2110.08669
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(m2/3n2/3log2/3 (n/√(m))+(m+n)log n) time. This improves the previously best deterministic algorithm [Agarwal, 1990] by a factor of log2.22n and improves the previously best randomized algorithm [Agarwal, Matoušek, and Schwarzkopf, 1998] by a factor of log1/3n in certain cases (e.g., when m=Θ(n)). For the segment case, we present a deterministic algorithm of O(n2/3m2/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 log2.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(m2/3K1/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.