Notes on computing peaks in k-levels and parametric spanning trees
Katoh, Naoki · Tokuyama, Takeshi
Original · EN
We give an algorithm to compute all the local peaks in the k-level of an arrangement of n lines in O(n n) + O((kn)²/³) time. We can also find τ largest peaks in O(n ² n) + O((τn)²/³) time. Moreover, we consider the longest edge in a parametric minimum spanning tree (in other words, a bottleneck edge for connectivity), and give an algorithm to compute the parameter value (within a given interval) maximizing/minimizing the length of the longest edge in MST. The time complexity is O(n⁸/⁷k¹/⁷ + n k¹/³)
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.