When crossings count — approximating the minimum spanning tree

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

When crossings count — approximating the minimum spanning tree

Full text

Pdf (1.07 MB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the sixteenth annual symposium on Computational geometry table of contents

Clear Water Bay, Kowloon, Hong Kong

Pages: 166 - 175

Year of Publication: 2000

ISBN:1-58113-224-7

Authors

Sariel Har-Peled	Department of Computer Science, D340 Levine Science Research Center; Duke University, Box 90129; Durham, NC
Piotr Indyk	Department of Computer Science, Stanford University

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 12, 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/336154.336197 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.

	AF97	Boris Aronov , Steven Fortune, Average-case ray shooting and minimum weight triangulations, Proceedings of the thirteenth annual symposium on Computational geometry, p.203-211, June 04-06, 1997, Nice, France [doi>10.1145/262839.262972]
	Aga91	P.K. Agarwal. Intersection and Decomposition Algorithms for Planar Arrangements. Cambridge University Press, New York, NY, 1991.
	Aga97	Pankaj K. Agarwal, Range searching, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
	AMS98	Pankaj K. Agarwal , Jirí Matousek , Otfried Schwarzkopf, Computing Many Faces in Arrangements of Lines and Segments, SIAM Journal on Computing, v.27 n.2, p.491-505, April 1998 [doi>10.1137/S009753979426616X]
	BDS95	M. de Berg, K. Dobrindt, and O. Schwarzkopf. On lazy randomized incremental construction. Discrete Comput. Geom., 14:261-286, 1995.
	EM98	Lectures on Proof Verification and Approximation Algorithms. (the book grow out of a Dagstuhl Seminar, April 21-25, 1997), January 1998
	Epp95	D. Eppstein. Dynamic Euclidean minimum spanning trees and extrema of binary functions. Discrete Comput. Geom., 13:111-122, 1995.
	Epp98	David Eppstein, Fast hiearchical clustering and other applications of dynamic closet pairs, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.619-628, January 25-27, 1998, San Francisco, California, United States
	GHS91	L.J. Guibas, J. Hershberger, and J. Snoeyink. Compact interval trees: a data structure for convex hulls. Internat. J. Comput. Geom. Appl., 1 (1):1-22, 1991.
	GIV99	A. Goel, P. Indyk, and K. Varadarajan. Reductions among high-dimensional geometric problems. menuscript, 1999.
	HPS99	S. Har-Peled and M. Sharir. On-line point location in planar arrangements and its applications. manuscript., 1999.
	IM98	Piotr Indyk , Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.604-613, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276876]
	Ind00	Piotr Indyk, Dimensionality reduction techniques for proximity problems, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.371-378, January 09-11, 2000, San Francisco, California, United States
	JL84	W.B. Johnson and J. Lindenstrauss. Extensions of lipshitz mapping into hilbert space. Contemporary Mathematics, 26:189-206, 1984.
	KOR98	Eyal Kushilevitz , Rafail Ostrovsky , Yuval Rabani, Efficient search for approximate nearest neighbor in high dimensional spaces, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.614-623, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276877]
	MR95	Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
	MWW91	Jiří Matoušek , Emo Welzl , Lorenz Wernisch, Discrepancy and &egr; approximations for bounded VC-dimension, Proceedings of the 32nd annual symposium on Foundations of computer science, p.424-430, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185401]
	PA95	Janos Pach and Pankaj K. Agarwal. Combinatorial Geometry. John Wiley & Sons, New York, NY, 1995.
	Wel92	Emo Welzl, On Spanning Trees with Low Crossing Numbers, Data Structures and Efficient Algorithms, Final Report on the DFG Special Joint Initiative, p.233-249, January 1992

CITED BY 3

	Sariel Har-Peled , Micha Sharir, Online point location in planar arrangements and its applications, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.57-66, January 07-09, 2001, Washington, D.C., United States
	Boris Aronov , Sariel Har-Peled, On approximating the depth and related problems, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Rajeev Kumar , P.K. Singh , Bhargab B. Bhattacharya, Biobjective evolutionary and heuristic algorithms for intersection of geometric graphs, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA