The Maximum-Level Vertex in an Arrangement of Lines
The Maximum-Level Vertex in an Arrangement of Lines
复制标题
DOI：
10.1007/s00454-021-00338-9
复制
发表时间：
2020-03
影响因子：
0.8
通讯作者：
D. Halperin;Sariel Har-Peled;K. Mehlhorn;Eunjin Oh;M. Sharir
中科院分区：
文献类型：
--
作者：
D. Halperin;Sariel Har-Peled;K. Mehlhorn;Eunjin Oh;M. Sharir
设L是平面上n条直线的集合，不一定在一般位置。本文提出了一个求最大水平集的所有顶点的有效算法，其中顶点的水平是L中严格低于v的线的数目。在de贝格et al.（Computational Geometry.算法与应用Springer，柏林（2008）），似乎比乍一看要难得多，因为这个顶点可能不在线的上包络上。我们首先假设L的所有线都是不同的，并区分两种情况，这取决于L的上包络是否包含有界边。在前一种情况下，我们证明了L中通过任意最高层顶点的线的个数仅为。在后一种情况下，我们建立了一个类似的性质，保持后，我们删除了一些线，是入射到上包络的单个顶点。我们提出的算法，运行，在这两种情况下，在optimaltime。然后，我们考虑L的线不一定是不同的情况。这种设置更具挑战性，对于这种情况下，我们提出了一种算法，计算所有的最高级别的顶点的时间。最后，我们考虑一个相关的组合问题退化的安排，其中许多线可能会在一个单一的点相交，但所有的线是不同的：我们绑定的复杂性的加权k-levelin这样的安排，其中一个顶点的权重是通过顶点的线的数量。我们表明，在这种情况下的界限，这与相应的非退化安排的界限相匹配，我们使用这个界限在我们的算法之一的分析。
AbstractLetLbe a set ofnlines in the plane, not necessarily in general position. We present an efficient algorithm for finding all the vertices of the arrangementof maximum level, where the level of a vertexvis the number of lines ofLthat pass strictly belowv. 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 ofLare distinct, and distinguish between two cases, depending on whether or not the upper envelope ofLcontains a bounded edge. In the former case, we show that the number of lines ofLthat passaboveany maximum level vertexis only. 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 optimaltime. We then consider the case where the lines ofLare 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. 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 theweightedk-levelin 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, which matches the corresponding bound for non-degenerate arrangements, and we use this bound in the analysis of one of our algorithms.