RECTILINEAR STEINER TREE HEURISTICS AND MINIMUM SPANNING TREE ALGORITHMS USING GEOGRAPHIC NEAREST NEIGHBORS

We study the application of the geographic nearest neighbor approach t o two problems. The first problem is the construction of an approximat ely minimum length rectilinear Steiner tree for a set of n points in t he plane. For this problem, we introduce a variation of a subgraph of size O(n) used by Yao [31] for constructing minimum spanning trees. Us ing this subgraph, we improve the running times of the heuristics disc ussed by Bern [6] from O(n(2) log n) to O(n log(2) n). The second prob lem is the construction of a rectilinear minimum spanning tree for a s et of n noncrossing line segments in the plane. We present an optimal O(n log n) algorithm for this problem. The rectilinear minimum spannin g tree for a set of points can thus be computed optimally without usin g the Voronoi diagram. This algorithm can also be extended to obtain a rectilinear minimum spanning tree for a set of nonintersecting simple polygons.