A MST(minimum spanning tree) is necessarily a MBST(minimum bottleneck spanning tree).
Given a set of points in a 2D plane with the edges of the weight of the Euclidean distance between each pair of point, I want to find the minimum bottleneck edge in the spanning tree (the maximum-weighted edge).
According to my limited knowledge in this field and research on the internet, the best way to calculate this using the MST approach is to do a Delaunay triangulation of the given points, and use the fact that the MST of these points is a subset of the triangulation and then run Kruskal's or Prim's algorithm. Then all I need to do is to find the maximum weight in the MST.
I am wondering if I can do this more efficiently by building a MBST, as I am only looking for the bottleneck edge.
Thanks in advance.
Edit: my current way to find it, both using MST or MBST calculates the weight of all V * (V-1) / 2
edges first, which I consider quite inefficient. I'd like to know if there's an alternative around this.