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 - Funding Information:
The authors thank Michal Kleinbort and Shahar Shamai for pointing out the difficulty of the problem of finding the maximum-level vertex. Work by Dan Halperin has been supported in part by the Israel Science Foundation (Grants No. 825/15 and 1736/19), by NSF/US-Israel-BSF (Grant No. 2019754), by the Israel Ministry of Science and Technology (Grant No. 103129), by the Blavatnik Computer Science Research Fund, and by the Yandex Machine Learning Initiative for Machine Learning at Tel Aviv University. Work by Sariel Har-Peled was supported by an NSF AF award CCF-1907400. Work by Eunjin Oh was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (Grant No. 2020R1C1C1012742). Work by Micha Sharir has been supported in part by Grant 260/18 from the Israel Science Foundation, by Grant G-1367-407.6/2016 from the German-Israeli Foundation for Scientific Research and Development, and by the Blavatnik Computer Science Research Fund.
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 -