Fast expected-time and approximation algorithms for geometric minimum spanning trees

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fast expected-time and approximation algorithms for geometric minimum spanning trees

Full text

Pdf (633 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the sixteenth annual ACM symposium on Theory of computing table of contents

Pages: 342 - 348

Year of Publication: 1984

ISBN:0-89791-133-4

Author

Kenneth L. Clarkson

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 16, Citation Count: 3

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/800057.808699 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	C. Berge and A. Ghouila-Houri. Programming,Games, and Transportation Networks,. John Wiley, New York, 1965.
	2	J. L. Bentley, H. Gabow, and R. E. Tarjan. Scaling and related techniques for geometry problems. These proceedings.
	3	Jon Louis Bentley , Bruce W. Weide , Andrew C. Yao, Optimal Expected-Time Algorithms for Closest Point Problems, ACM Transactions on Mathematical Software (TOMS), v.6 n.4, p.563-580, Dec. 1980 [doi>10.1145/355921.355927]
	4	K .L . Clarkson. Fast algorithms for the all nearest neighbors problem. Proc. 24th Symp. on Foundations of Computer Science, Tucson, AZ, November 1983, pp. 226-232.
	5	K. L. Clarkson. A nearly linear expected time algorithm for minimum spanning trees in coordinate spaces. Unpublished manuscript, 1983.
	6	L. Devroye. Average time behavior of distributive sorting algorithms. Tech. Rep. No. SOCS 79.4, School of Computer Science, McGill University, 1979.
	7	D. Dobkin. Personal communication.
	8	M. L. Fredman and R. E. Tarjan. Fibonacci heaps and their uses in network optimization algorithms. Unpublished manuscript, 1984.
	9	L. J. Guibas and J. Stolfi. On computing all north-east nearest neighbors in the L1 metric. Unpublished manuscript.
	10	D. Kirkpatrick. Optimal search in planar subdivisions. SIAM Journal of Computing, Volume 12 (1983), pp. 28-35.
	11	J. B. Kruskal, Jr. On the shortest spanning subgraph of a graph and the traveling salesman problem. Proc. Amer. Math. Soc., Volume 7 (1956), pp. 48-50.
	12	G. Lueker. A survey of address calculation techniques with unknown input distributions. Unpublished manuscript, 1983.
	13	D. T. Lee and C.K. Wong. Voronoi diagrams in L&1 (Loo) metrics with 2-dimensional storage applications. SIAM Journal of Computing, Volume 9 (1980), pp. 200-211.
	14	M. I. Shamos and D. Hoey. Closest-point problems. Proc. 16th Symp. on Foundations of Computer Science, 1975, pp. 151-162.
	15	J. Stolfi. Personal communication.
	16	Kenneth J. Supowit, The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees, Journal of the ACM (JACM), v.30 n.3, p.428-448, July 1983 [doi>10.1145/2402.322386]
	17	Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975 [doi>10.1145/321879.321884]
	18	A. C. Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM Journal of Computing, Volume 11 (1982), Number 4, pp. 721-736.

CITED BY 3

	Pankaj K. Agarwal , Herbert Edelsbrunner , Otfried Schwarzkopf , Emo Welzl, Euclidean minimum spanning trees and bichromatic closest pairs, Proceedings of the sixth annual symposium on Computational geometry, p.203-210, June 07-09, 1990, Berkley, California, United States
	Drago Krznaric , Christos Levcopoulos , Bengt J. Nilsson, Minimum spanning trees in d dimensions, Nordic Journal of Computing, v.6 n.4, p.446-461, Winter 1999
	Jeffrey S. Salowe, Construction of multidimensional spanner graphs, with applications to minimum spanning trees, Proceedings of the seventh annual symposium on Computational geometry, p.256-261, June 10-12, 1991, North Conway, New Hampshire, United States