The Maximum-Level Vertex in an Arrangement of Lines
$
\newcommand{\Re}{\mathbb{R}}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\SetX}{\mathsf{X}}
\newcommand{\rad}{r}
\newcommand{\A}{\mathcal{A}}
\newcommand{\Mh}[1]{#1}
\newcommand{\query}{q}
\newcommand{\eps}{\varepsilon}
\newcommand{\VorX}[1]{\mathcal{V} \pth{#1}}
\newcommand{\Polygon}{\mathsf{P}}
\newcommand{\IntRange}[1]{[ #1 ]}
\newcommand{\Space}{\overline{\mathsf{m}}}
\newcommand{\pth}[2][\!]{#1\left({#2}\right)}
\newcommand{\polylog}{\mathrm{polylog}}
\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\pt}{p}
\newcommand{\distY}[2]{\left\| {#1} - {#2} \right\|}
\newcommand{\ptq}{q}
\newcommand{\pts}{s}$
Dan Halperin,
Sariel Har-Peled,
Kurt Mehlhorn,
Eunjin Oh, and
Micha Sharir.
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~\cite{bcko-08}, appears to be much harder than it
seems at first sight,
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 \emph{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 for this case we present 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 \emph{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.
PDF.
:
arXiv
:
DBLP.
Last modified: Mon 2022-07-25 14:01:33 UTC 2022 by Sariel Har-Peled