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.
Haitao Wang (Thu,) studied this question.