Jon Louis Bentley
Bruce W. Weide
Andrew C. Yao
- 1 AHO, A V, HOPCROFT, J.E., AND ULLMAN, J.D The Design and Analysts of Computer Algorithms. Addison-Wesley, Reading, Mass, 1974. Google Scholar
- 2 BENTLEY, J.L. Multidimensional divide-and-conquer. Commun. ACM 23, 4 (April 1980), 214- 229 Google Scholar
- 3 BENTLEY, J L., AND FRIEDMAN, J.H. Fast algorithms for constructing mmtmal spannmg trees in coordinate spaces IEEE Trans. Comput C-27, 2 (Feb. 1978), 97-105.Google Scholar
- 4 BENTLEY, J.L, AND FRIEDMAN, J.H. Data structures for range searching. Comput. Surv. 11, 4 (Dec. 1979), 398-409. Google Scholar
- 5 CHERITON, D, AND TARJAN, R E. Finding minimum spanning trees SIAM J. Comput. 5, 4 (Dec 1976), 724-742Google Scholar
- 6 DOBKIN, D, AND LIPTON, l~ J Multidimensional searching problems. SIAM J. Comput 5, 2 (June 1976), 181-186.Google Scholar
- 7 FORTUNE, S., AND HOPCROFT, J E A note on Rabm's nearest-neighbor algorithm. Inf. Process. Lett. 8, 1 (Jan. 1979), 20-23.Google Scholar
- 8 FRIEDMAN, J.H, BENTLEY, J.L., AND FINKEL, R.A. An algorithm for finding best matches m logarithmic expected time. ACM Trans. Math. Softw. 3, 3 (Sept. 1977), 209-226. Google Scholar
- 9 HORSPOOL, R N. Constructing the Voronol chagram in the plhne Tech Rep SOCS-79.12, Comput Sci School, McGill Umv, Montreal, Canada, July 1979.Google Scholar
- 10 KIRKPATRICK, D G Efficmnt computation of continuous skeletons. Proc. 20th IEEE Syrup Foundatmns of Computer Sctence, Oct. 1979, pp 18-27.Google Scholar
- 11 LIPTON, R.J., AND TARJAN, R.E. Application of a planar separator theorem. Proc 18th IEEE Symp. Foundatmns of Computer Science, Oct. 1977, pp. 162-170.Google Scholar
- 12 MONIER, L. Personal commumcatlon of Lores Morner of the Umversit6 de Parls-Sud to J.L. Bentley, June 1978.Google Scholar
- 13 PREPARATA, F.P., AND HONG, S.J. Convex hull of fimte sets of points m two and three dimensions. Commun. ACM 20, 2 (Feb. 1977), 87-93. Google Scholar
- 14 RABIN, M O. Probabilistic algorithms, m Algorithms and Complextty: New Dwectmns and Recent Results, J.F. Traub (Ed.), Academm Press, New York, 1976, pp. 21-39.Google Scholar
- 15 ROHLF, F J A probabfllStlC mmnnum spannmg tree algorithm. Inf. Process. Lett. 7, 1 (Jan 1978), 44-48.Google Scholar
- 16 SHAMOS, M.I Computational geometry Ph.D. Dissertation, Yale Umv., New Haven, Conn., May 1978. Google Scholar
- 17 SHAMOS, M.I, AND HOEY, D. Closest-point problems Proc 16th IEEE Symp. Foundatmns of Computer Scwnce, Oct 1975, pp. 151-162.Google Scholar
- 18 WEIDE, B.W. Statistical methods m algorithm design and analysis. Ph.D. Dissertation, Carnegm- Mellon Umv, Pittsburgh, Pa, Aug 1978 (Appeared as CMU Comput Sci. Rep. CMU-CS-78- 142 ) Google Scholar
- 19 YAO, A.C. An O({E{log logl V{) algorithm for findmg mmnnum spanning trees. Inf. Process. Lett. 4, 1 (Sept 1975), 21-23Google Scholar
- 20 YAO, A C On constructing minimum spanning trees m k-dimensional space and related problems. Res. Rep STAN-CS-77-642, Dep. Comput. Sci., Stanford Univ., Calif., 1977. Google Scholar
- 21 YUVAL, G. Finding nearest neighbors. Inf. Process. Lett 5, 3 (Aug. 1976), 63-65Google Scholar
Index Terms
- Optimal Expected-Time Algorithms for Closest Point Problems
Recommendations
An algorithm for approximate closest-point queries
SCG '94: Proceedings of the tenth annual symposium on Computational geometryThis paper gives an algorithm for approximately solving the post office problem: given n points (called sites) in d dimensions, build a data structure so that, given a query point q, a closest site to q can be found quickly. The algorithm is also given ...
Algorithms for Closest and Farthest String Problems via Rank Distance
Theory and Applications of Models of ComputationAbstractA new distance between strings, termed rank distance, was introduced by Dinu (Fundamenta Informaticae, 2003). Since then, the properties of rank distance were studied in several papers. In this article, we continue the study of rank distance. More ...
Comments