2026-09-05T11:58:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25901 2026-06-23T13:00:29Z ddc:004 open_access

An Optimal Algorithm for Computing Many Faces in Line Arrangements Wang, Haitao Many faces line arrangements cuttings Γ-algorithms decision tree complexities 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]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Haitao Wang 2026 Is Part Of LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2026.95 urn:nbn:de:0030-drops-259012 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.95 eng https://creativecommons.org/licenses/by/4.0/legalcode