An Optimal Algorithm for Computing Many Faces in Line Arrangements

Given a set of m points and a set of n lines in the plane, we consider the classical problem of computing the faces of the arrangement of the lines that contain at least one point. We present an algorithm of O (m^2/3 n^2/3 + (n+m) log n) time for the problem. We also prove that this matches the lower bound under the algebraic decision tree model and thus our algorithm is optimal. In particular, when m = n, the runtime is O (n^4/3), which matches the worst case combinatorial complexity Ω (n^4/3) of all output faces. This is the first optimal algorithm since the problem was first studied more than three decades ago Edelsbrunner, Guibas, and Sharir, SoCG 1988.