Notes on computing peaks in k-levels and parametric spanning trees
<|reference_start|>Notes on computing peaks in k-levels and parametric spanning trees: 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})$<|reference_end|>
@article{katoh2001notes,
    title={Notes on computing peaks in k-levels and parametric spanning trees},
    author={Naoki Katoh and Takeshi Tokuyama},
    journal={arXiv preprint arXiv:cs/0103024},
    year={2001},
    archivePrefix={arXiv},
    eprint={cs/0103024},
    primaryClass={cs.CG cs.DS}
}