The maximum-level vertex in an arrangement of lines

DOI10.1007/S00454-021-00338-9MaRDI QIDQ2117347zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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