Notes on computing peaks in k-levels and parametric spanning trees
| dc.creator | Katoh, Naoki | |
| dc.creator | Tokuyama, Takeshi | |
| dc.date | 2001-03-29 | |
| dc.date.accessioned | 2026-07-07T03:17:02Z | |
| dc.date.available | 2026-07-07T03:17:02Z | |
| dc.description | 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 $τ$ largest peaks in $O(n \log ^2 n) + \tilde{O}((τ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})$ | |
| dc.description | ACM SCG'01 | |
| dc.identifier | https://arxiv.org/abs/cs/0103024 | |
| dc.identifier | http://arxiv.org/abs/cs/0103024 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/30577 | |
| dc.subject | Computational Geometry | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | F2.2 | |
| dc.title | Notes on computing peaks in k-levels and parametric spanning trees | |
| dc.type | text |