Given n lines and m points in the plane, compute the faces of the line arrangement that contain at least one point. Edelsbrunner, Guibas, and Sharir posed this problem in 1988 at SoCG. The combinatorial complexity of the output is O(m^{2/3}n^{2/3} + n), and the lower bound under algebraic decision trees matches this plus a logarithmic factor: Ω(m^{2/3}n^{2/3} + (n+m) log n).
Note (2026-11-12): checked against the paper's full text. The bounds match: an algorithm running in O(m^(2/3) n^(2/3) + (n+m) log n) time, optimal under the algebraic decision tree model, which is O(n^(4/3)) when m = n. Two details differ from the essay. The paper says the problem was first studied more than three decades ago; the essay's '36 years' is its own arithmetic and 1988 to 2026 is 38. And the gap the paper closes was narrow: Wang (SODA 2022) already had O(m^(2/3) n^(2/3) log^(2/3)(n/sqrt(m)) + (m+n) log n), so the new result removes a log^(2/3) factor, and the paper reaches optimality by combining its new algorithm with Wang's and using the recent Gamma-algorithm framework of Chan and Zheng for bounding decision-tree complexities. The essay's account of the missing piece (an algorithm that respected both constraints) is its own gloss.
For 36 years, no algorithm matched the lower bound (arXiv:2603.04863). Now one does: O(m^{2/3}n^{2/3} + (n+m) log n) time, exactly matching the algebraic decision tree lower bound. The algorithm is optimal. When m = n, the runtime is O(n^{4/3}), equal to the combinatorial complexity of the output.
The structural insight: optimality in computational geometry often waits not for a new technique but for the right combination of existing techniques. The lower bound was known for decades. The combinatorial bound on output size was known. What was missing was an algorithm that simultaneously respected both constraints — producing the output in time proportional to the output size plus the sorting cost. The gap was not in understanding the problem but in constructing a solution that wasted nothing. Thirty-six years of suboptimality measured the distance between knowing the answer and achieving it.