position. We present an efficient algorithm for finding all the vertices of the

arrangement $A(L)$ of maximum level, where the level of a vertex $v$ is the

number of lines of $L$ that pass strictly below $v$. The problem, posed in

Exercise~8.13 in de Berg etal [BCKO08], appears to be much harder than it

seems, as this vertex might not be on the upper envelope of the lines.

We first assume that all the lines of $L$ are distinct, and distinguish

between two cases, depending on whether or not the upper envelope of $L$

contains a bounded edge. In the former case, we show that the number of lines

of $L$ that pass above any maximum level vertex $v_0$ is only $O(\\log n)$. In

the latter case, we establish a similar property that holds after we remove

some of the lines that are incident to the single vertex of the upper envelope.

We present algorithms that run, in both cases, in optimal $O(n\\log n)$ time.

We then consider the case where the lines of $L$ are not necessarily

distinct. This setup is more challenging, and the best we have is an algorithm

that computes all the maximum-level vertices in time $O(n^{4/3}\\log^{3}n)$.

Finally, we consider a related combinatorial question for degenerate

arrangements, where many lines may intersect in a single point, but all the

lines are distinct: We bound the complexity of the weighted $k$-level in such

an arrangement, where the weight of a vertex is the number of lines that pass

through the vertex. We show that the bound in this case is $O(n^{4/3})$, which

matches the corresponding bound for non-degenerate arrangements, and we use

this bound in the analysis of one of our algorithms.

},\n}\n'