Efficient Rectilinear Minimum Spanning Tree Without Delaunay Triangulation

Given a set of points in a plane, a spanning tree is a set of edges that connects all the points and contains no cycles. If each edge is weighted using the rectilinear distance metric, the rectilinear minimum spanning tree is a tree whose sum of edge weights is minimum. A naive approach to construct the spanning tree enumerates edges on all pairs of points and takes at least Ω() time. More efficient approaches exploit the planarity property to construct a Delaunay triangulation of the points, and find the minimum spanning tree considering only the edges in the triangulation. In this paper, we define a spanning graph which is more natural than Delaunay triangulation for minimum spanning tree construction and design an efficient algorithm to construct a rectilinear minimum spanning tree without resorting to Delaunay triangulation