P50: Enumeration of the orthogonal $k$ best spanning trees in a plane with $n$ points
P50: Enumeration of the orthogonal $k$ best spanning trees in a plane with $n$ points
Input:
$n$ points in a plane
Output:
The orthogonal $k$ best spanning trees of the given points.
Complexity:
$O(k^2 + k n \log \log (n/k) + n \log n)$ total time.
Comment:
An orthogonal spanning tree in a plane is a spanning tree of the complete graph whose vertices are all given points and the weight of an edge equal to the $L_1$ distance between the corresponding vertices.