Approximate range searching

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Approximate range searching

Full text

Pdf (958 KB)

Source

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

Vancouver, British Columbia, Canada

Pages: 172 - 181

Year of Publication: 1995

ISBN:0-89791-724-3

Authors

Sunil Arya	Max-Planck-Institut für Informatik, D-66123 Saarbrücken, Germany
David M. Mount	Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, College Park, MD

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): 3, Downloads (12 Months): 27, Citation Count: 13

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/220279.220298 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	Sunil Arya , David M. Mount , Nathan S. Netanyahu , Ruth Silverman , Angela Wu, An optimal algorithm for approximate nearest neighbor searching, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.573-582, January 23-25, 1994, Arlington, Virginia, United States
	2	Jon Louis Bentley, K-d trees for semidynamic point sets, Proceedings of the sixth annual symposium on Computational geometry, p.187-197, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98564]
	3	H. BrSnnimann, B. Chazelle, and J. Pach. How hard is halfspace range searching. Discrete Comput. Geom., 10:143-155, 1993.
	4	Paul B. Callahan , S. Rao Kosaraju, A decomposition of multi-dimensional point-sets with applications to k-nearest-neighbors and n-body potential fields (preliminary version), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.546-556, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129766]
	5	Paul B. Callahan , S. Rao Kosaraju, Algorithms for dynamic closest pair and n-body potential fields, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.263-272, January 22-24, 1995, San Francisco, California, United States
	6	B. Chazelle. Lower bounds on the complexity of polytope range searching. J. Amer. Math. Soc., 2:637-666, 1989.
	7	B. Chazelle , E. Welzl, Quasi-optimal range searching in spaces of finite VC-dimension, Discrete & Computational Geometry, v.4 n.5, p.467-489, 1989 [doi>10.1007/BF02187743]
	8	K. L. Clarkson. Fast algorithms for the all nearest neighbors problem. In Proc. 2jth Ann. IEEE Sympos. on the Found. Comput. Sci., pages 226-232, 1983.
	9	N. Faxvardin and J. W. Modestino. Ratedistortion performance of DPCM schemes for autoregressive sources, iEEE Transactions on information Theory, 31:402-418, 1985.
	10	J. Matou~ek. Range searching with efficient hierarchical cuttings. Discrete Comput. Geom., 10(2):157-182, 1993.
	11	Mark H. Overmars, Point location in fat subdivisions, Information Processing Letters, v.44 n.5, p.261-265, Dec. 21, 1992 [doi>10.1016/0020-0190(92)90211-D]
	12	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	13	Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
	14	P. M. Vaidya, An O(n log n) algorithm for the all-nearest-neighbors problem, Discrete & Computational Geometry, v.4 n.2, p.101-115, Jan. 1989 [doi>10.1007/BF02187718]

CITED BY 13

	Sunil Arya , David M. Mount , Nathan S. Netanyahu , Ruth Silverman , Angela Y. Wu, An optimal algorithm for approximate nearest neighbor searching fixed dimensions, Journal of the ACM (JACM), v.45 n.6, p.891-923, Nov. 1998
	Christian A. Duncan , Michael T. Goodrich , Stephen Kobourov, Balanced aspect ratio trees: combining the advantages of k-d trees and octrees, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.300-309, January 17-19, 1999, Baltimore, Maryland, United States
	Tapas Kanungo , David M. Mount , Nathan S. Netanyahu , Christine Piatko , Ruth Silverman , Angela Y. Wu, The analysis of a simple k-means clustering algorithm, Proceedings of the sixteenth annual symposium on Computational geometry, p.100-109, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	Timothy M. Chan, Approximate nearest neighbor queries revisited, Proceedings of the thirteenth annual symposium on Computational geometry, p.352-358, June 04-06, 1997, Nice, France
	David M. Mount , Nathan S. Netanyahu , Jacqueline Le Moigne, Improved algorithms for robust point pattern matching and applications to image registration, Proceedings of the fourteenth annual symposium on Computational geometry, p.155-164, June 07-10, 1998, Minneapolis, Minnesota, United States
	Ertem Tuncel , Hakan Ferhatosmanoglu , Kenneth Rose, VQ-index: an index structure for similarity searching in multimedia databases, Proceedings of the tenth ACM international conference on Multimedia, December 01-06, 2002, Juan-les-Pins, France
	Giuseppe Amato , Fausto Rabitti , Pasquale Savino , Pavel Zezula, Region proximity in metric spaces and its use for approximate similarity search, ACM Transactions on Information Systems (TOIS), v.21 n.2, p.192-227, April 2003
	Edgar Chávez , Gonzalo Navarro, Probabilistic proximity search: fighting the curse of dimensionality in metric spaces, Information Processing Letters, v.85 n.1, p.39-46, 16 January 2003
	Benjamin Bustos , Gonzalo Navarro, Probabilistic proximity searching algorithms based on compact partitions, Journal of Discrete Algorithms, v.2 n.1, p.115-134, March 2004
	Sergey Bereg , Michael Segal, Dynamic algorithms for approximating interdistances, Nordic Journal of Computing, v.11 n.4, p.344-355, December 2004
	Hakan Ferhatosmanoglu , Ertem Tuncel , Divyakant Agrawal , Amr El Abbadi, High dimensional nearest neighbor searching, Information Systems, v.31 n.6, p.512-540, September 2006
	Fang Yi , Xiong Sheng Wu, Pattern matching using the Hausdorff distance, Proceedings of the 4th WSEAS International Conference on Artificial Intelligence, Knowledge Engineering Data Bases, p.1-8, February 13-15, 2005, Salzburg, Austria
	Fang Yi , Xiong ShengWu, Pattern matching using the Hausdorff distance, Proceedings of the 4th WSEAS International Conference on Applied Mathematics and Computer Science, p.1-8, April 25-27, 2005, Rio de Janeiro, Brazil