The maximum-level vertex in an arrangement of lines

DOI10.1007/S00454-021-00338-9zbMATH Open1485.52019arXiv2003.00518OpenAlexW4205305123MaRDI QIDQ2117347FDOQ2117347

Authors: Dan Halperin, Sariel Har-Peled, K. Mehlhorn, Eunjin Oh, Micha Sharir 

Publication date: 21 March 2022

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Abstract: 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(logn)$. 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(nlogn)$ 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}lo{g}^{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.

Full work available at URL: https://arxiv.org/abs/2003.00518

Recommendations

• Constructing Levels in Arrangements and Higher Order Voronoi Diagrams
• Constructing Arrangements of Lines and Hyperplanes with Applications
• AN OPTIMAL ALGORITHM FOR COMPUTING (≤K)-LEVELS, WITH APPLICATIONS
• On levels in arrangements of lines, segments, planes, and triangles
• On Computing the Centroid of the Vertices of an Arrangement and Related Problems

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Planar arrangements of lines and pseudolines (aspects of discrete geometry) (52C30) Combinatorial complexity of geometric structures (52C45)

Cites Work

• Applications of random sampling in computational geometry. II
• Computational geometry. Algorithms and applications.
• Improved bounds for planar \(k\)-sets and related problems
• An optimal algorithm for intersecting line segments in the plane
• Maintenance of configurations in the plane
• Finding the upper envelope of n line segments in O(n log n) time
• AN OPTIMAL ALGORITHM FOR COMPUTING (≤K)-LEVELS, WITH APPLICATIONS
• A characterization of planar graphs by pseudo-line arrangements
• Constructing Belts in Two-Dimensional Arrangements with Applications
• The number of small semispaces of a finite set of points in the plane

Cited In (2)

• Notes on computing peaks in \(k\)-levels and parametric spanning trees
• On the zone complexity of a vertex

This page was built for publication: The maximum-level vertex in an arrangement of lines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2117347)