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

Naoki Katoh, Takeshi Tokuyama

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 peak…