TY - JOUR
T1 - The Maximum-Level Vertex in an Arrangement of Lines
AU - Halperin, Dan
AU - Har-Peled, Sariel
AU - Mehlhorn, Kurt
AU - Oh, Eunjin
AU - Sharir, Micha
N1 - Publisher Copyright:
© 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.
PY - 2022/3
Y1 - 2022/3
N2 - 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 et al. (Computational Geometry. Algorithms and Applications. Springer, Berlin (2008)), 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 above any maximum level vertex v 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(nlog 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(n4/3log3n). 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 weightedk-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(n4 / 3) , which matches the corresponding bound for non-degenerate arrangements, and we use this bound in the analysis of one of our algorithms.
AB - 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 et al. (Computational Geometry. Algorithms and Applications. Springer, Berlin (2008)), 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 above any maximum level vertex v 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(nlog 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(n4/3log3n). 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 weightedk-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(n4 / 3) , which matches the corresponding bound for non-degenerate arrangements, and we use this bound in the analysis of one of our algorithms.
UR - http://www.scopus.com/inward/record.url?scp=85122668232&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85122668232&partnerID=8YFLogxK
U2 - 10.1007/s00454-021-00338-9
DO - 10.1007/s00454-021-00338-9
M3 - Article
AN - SCOPUS:85122668232
SN - 0179-5376
VL - 67
SP - 439
EP - 461
JO - Discrete and Computational Geometry
JF - Discrete and Computational Geometry
IS - 2
ER -