Notes on computing peaks in k-levels and parametric spanning trees

Abstract

We give an algorithm to compute all the local peaks in the $k$-level of an arrangement of $n$ lines in $O(n\log n)+\tilde{O}((kn{)}^{2/3})$ time. We can also find $\tau$ largest peaks in $O(n{\log }^{2}n)+\tilde{O}((\tau n{)}^{2/3})$ 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 $\tilde{O}(n^{8/7}{k}^{1/7}+n{k}^{1/3})$

ACM SCG'01