Datensatz

Zusammenfassung

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 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.