The Maximum-Level Vertex in an Arrangement of Lines

Dan Halperin, Sariel Har-Peled, Kurt Mehlhorn +2

Let $L$ be a set of $n$ lines in the plane, not necessarily in general position. We present an efficient algorithm for finding all the vertices of the arrangement $A(L)$ of maximum…