- 1.S. Arya, D. M. Mount, N. S. Netanyahu, R. Silverman, and A. Wu. An optimal algorithm for approximate nearest neighbor searching. In Proc. 5th A UM-SIAM Sympos. Discrete Algorithms, pages 573-582, 1994. Google ScholarDigital Library
- 2.J. L. Bentley. K-d trees for semidynamic point sets. In Proc. 6th Ann. A CM Sympos. Comput. Geom., pages 187-197, 1990. Google ScholarDigital Library
- 3.H. BrSnnimann, B. Chazelle, and J. Pach. How hard is halfspace range searching. Discrete Comput. Geom., 10:143-155, 1993.Google ScholarDigital Library
- 4.P. B. Callahan and S. R. Kosaraju. A decomposition of multi-dimensional point-sets with applications to k-nearest-neighbors and n-body potential fields. In Proc. 2jth Annu. A CM Sympos. Theory Comput., pages 546- 556, 1992. Google ScholarDigital Library
- 5.P.B. Callahan and S. R. Kosaraju. Algorithms for dynamic closest pair and n-body potential fields. In Proc. 6th A CM-SIAM Sympos. Discrete Algorithms, 1995. Google ScholarDigital Library
- 6.B. Chazelle. Lower bounds on the complexity of polytope range searching. J. Amer. Math. Soc., 2:637-666, 1989.Google ScholarCross Ref
- 7.B. Chazelle and E. Welzl. Quasi-optimal range searching in spaces of finite VC-dimension. Discrete Comput. Geom., 4:467-489, 1989.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 9.N. Faxvardin and J. W. Modestino. Ratedistortion performance of DPCM schemes for autoregressive sources, iEEE Transactions on information Theory, 31:402-418, 1985.Google Scholar
- 10.J. Matou~ek. Range searching with efficient hierarchical cuttings. Discrete Comput. Geom., 10(2):157-182, 1993.Google ScholarDigital Library
- 11.M. It. Overmars. Point location in fat subdivisions. Inform. Process. Lett., 44:261-265, 1992. Google ScholarDigital Library
- 12.F. P. Preparata and M. I. Shamos. Computational Geometry: an Introduction. Springer- Verlag, New York, NY, 1985. Google ScholarDigital Library
- 13.H. Samet. The Design and Analysis of Spatial Data Structures. Addison Wesley, Reading, MA, 1990. Google ScholarDigital Library
- 14.P. M. Vaidya. An O(n log n) algorithm for the all_nearest.neighbors problem. Discrete Cornput. Geom., 4:101-115, 1989.Google ScholarDigital Library
Index Terms
- Approximate range searching
Recommendations
An optimal algorithm for approximate nearest neighbor searching fixed dimensions
Consider a set of S of n data points in real d-dimensional space, Rd, where distances are measured using any Minkowski metric. In nearest neighbor searching, we preprocess S into a data structure, so that given any query point q∈ Rd, is the closest ...
Approximate range searching: The absolute model
Range searching is a well known problem in the area of geometric data structures. We consider this problem in the context of approximation, where an approximation parameter @e>0 is provided. Most prior work on this problem has focused on the case of ...
Comments