ISSN:
1432-0541
Keywords:
Spanning tree
;
Steiner tree
;
Heuristic algorithm
;
Computational geometry
;
Rectilinear distance
;
Nearest neighbor
;
Geographic nearest neighbor
;
Decomposable search problem
;
Range tree
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract We study the application of the geographic nearest neighbor approach to two problems. The first problem is the construction of an approximately minimum length rectilinear Steiner tree for a set ofn points in the plane. For this problem, we introduce a variation of a subgraph of sizeO(n) used by YaO [31] for constructing minimum spanning trees. Using this subgraph, we improve the running times of the heuristics discussed by Bern [6] fromO(n 2 log n) toO(n log2 n). The second problem is the construction of a rectilinear minimum spanning tree for a set ofn noncrossing line segments in the plane. We present an optimalO(n logn) algorithm for this problem. The rectilinear minimum spanning tree for a set of points can thus be computed optimally without using the Voronoi diagram. This algorithm can also be extended to obtain a rectilinear minimum spanning tree for a set of nonintersecting simple polygons.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01188713
Permalink
