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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
A. Aggarwal, B. Chazelle, L. Guibas, C. Ó'Dúnlaing, and C. Yap, Parallel Computational Geometry,Algorithmica,3 (1988), 293–327.
M. J. Atallah, R. Cole, and M. T. Goodrich, Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms,Proc. 28th IEEE Symp. on Foundations of Computer Science, 1987, pp. 151–160.
A. Baratz, Algorithms for Integrated Circuit Signal Routing, Ph.D. Thesis MIT/LCS/TR-248, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 1983.
J. L. Bentley, Decomposable Searching Problems,Inform. Process. Lett.,8 (1979), 244–251.
J. L. Bentley, Multidimensional Divide and Conquer,Comm. ACM,23 (1980), 214–229.
M. W. Bern, Two Probabilistic Results on Rectilinear Steiner Trees,Algorithmica,3 (1988), 191–204.
M. W. Bern and M. de Carvalho, A Greedy Heuristic for the Rectilinear Steiner Tree Problem, Technical Report No. UCB-CSD-87-306, Computer Science Division, University of California, Berkeley, CA, 1986.
B. Chazelle and B. Rosenburg, Computing Partial Sums in Multidimensional Arrays,Proc. 5th Ann. ACM Symp. on Computational Geometry, 1989, pp. 131–139.
K. Clarkson, Fast Expected-Time and Approximation Algorithms for Geometric Minimum Spanning Trees,Proc. 16th Ann. ACM Symp. on Theory of Computing, 1984, pp. 342–348.
K. Clarkson, Approximation Problems for Shortest Path Motion Planning,Proc. 19th Ann. ACM Symp. on Theory of Computing, 1987, pp. 56–65.
H. Edelsbrunner and M. H. Overmars, Batched Dynamic Solutions to Decomposable Searching Problems,J. Algorithms,6 (1985), 515–542.
M. L. Fredman and R. E. Tarjan, Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms,J. Assoc. Comput. Mach.,34 (1987), 596–615.
M. R. Garey and D. S. Johnson,Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, San Fransisco, CA, 1979.
F. K. Hwang, An0(n logn) Algorithm for Suboptimal Rectilinear Steiner Trees,IEEE Trans. Circuits and Systems,26 (1979), 75–77.
F. K. Hwang and D. S. Richards, Steiner Tree Problems,Networks,22 (1992), 55–89.
M. Imase and B. M. Waxman, Dynamic Steiner Tree Problem, Technical Report No. WUCS-89-11, Department of Computer Science, Washington University, St. Louis, MO, 1989.
J. W. Jaromczyk and M. Kowaluk, A Note on Relative Neighborhood Graphs,Proc. Third Ann. Symp. on Computational Geometry, 1987, pp. 233–241.
J. Katajainen, The Region Approach for Computing Relative Neighborhood Graphs in theL p Metric,Computing,40 (1988), 147–161.
S. K. Kim, Parallel Algorithms for the Segment-Dragging Problem, Unpublished Manuscript, Department of Computer Science and Engineering, University of Washington, Seattle, WA, 1989.
D. Richards, Fast Heuristic Algorithms for Rectilinear Steiner Trees,Algorithmica,4 (1989), 191–207.
K. J. Supowit, The Relative Neighborhood Graph with an Application to Minimum Spanning Trees,J. Assoc. Comput Mach.,30 (1983), 428–447.
R. E. Tarjan,Data Structures and Network Algorithms, SIAM, Philadelphia, PA, 1983.
G. T. Toussaint, The Relative Neighborhood Graph of a Finite Planar Set,Pattern Recognition,12 (1980), 261–268.
Y. C. Wee, Efficient Algorithms for Proximity Problems, Ph.D. Thesis, Department of Computer Science, SUNY, Albany, NY, 1989.
Y. C. Wee and S. Chaiken, An Optimal ParallelL 1 Metric Voronoi Diagram Algorithm,Proc. Second Canadian Conf. on Computational Geometry, 1990, pp. 60–65.
Y. C. Wee, S. Chaiken, and S. S. Ravi, Some Applications of the Geographic Nearest Neighbors Approach,Proc. 27th Ann. Allerton Conf. on Communication, Control, and Computing, 1989, pp. 555–563.
Y. C. Wee, S. Chaiken, and D. E. Willard, The Angle Restricted Voronoi Diagram,First Canadian Conference on Computational Geometry, 1989. (Also available as Technical Report No. 88-31, Department of Computer Science, SUNY, Albany, NY, 1988.)
D. E. Willard, New Data Structure for Orthogonal Range Queries,SIAM J. Comput.,14 (1985), 233–253.
D. E. Willard, Multidimensional Search Trees that Provides New Types of Memory Reductions,J. Assoc. Comput. Mach.,34 (1987), 845–858.
D. E. Willard and Y. C. Wee, Quasi-Valid Range Querying and Its Implications for Nearest-Neighbor Problems,Proc. 4th Ann. ACM Symp. on Computational Geometry, 1988, pp. 34–43.
A. C. Yao, On Constructing Minimum Spanning Trees ink-Dimensional Spaces and Related Problems,SIAM J. Comput.,11 (1982), 721–736.
Author information
Authors and Affiliations
Additional information
The results in this paper are a part of Y. C. Yee's Ph.D. thesis done at SUNY at Albany. He was supported in part by NSF Grants IRI-8703430 and CCR-8805782. S. S. Ravi was supported in part by NSF Grants DCI-86-03318 and CCR-89-05296.
Rights and permissions
About this article
Cite this article
Wee, Y.C., Chaiken, S. & Ravi, S.S. Rectilinear steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors. Algorithmica 12, 421–435 (1994). https://doi.org/10.1007/BF01188713
Issue Date:
DOI: https://doi.org/10.1007/BF01188713