Simple Algorithms for Enumerating Interpoint Distances and Finding K Nearest Neighbors

Simple Algorithms for Enumerating Interpoint Distances and Finding K Nearest Neighbors. Dickerson, M. T., Drysdale, Scot, R., & Sack, J.- International Journal of Computational Geometry \& Applications, 02(03):221--239, World Scientific Publishing Company, September, 1992.

Paper doi abstract bibtex

We present an O(n log n+k log k) time and O(n+k) space algorithm which takes as input a set of n points in the plane and enumerates the k smallest distances between pairs of points in nondecreasing order. We also present an O(n log n+kn log k) solution to the problem of finding the k nearest neighbors for each of n points. Both algorithms are conceptually very simple, are easy to implement, and are based on a common data structure: the Delaunay triangulation. Variants of the algorithms work for any convex distance function metric.

@article{ DICKERSON1992,
  abstract = {We present an O(n log n+k log k) time and O(n+k) space algorithm which takes as input a set of n points in the plane and enumerates the k smallest distances between pairs of points in nondecreasing order. We also present an O(n log n+kn log k) solution to the problem of finding the k nearest neighbors for each of n points. Both algorithms are conceptually very simple, are easy to implement, and are based on a common data structure: the Delaunay triangulation. Variants of the algorithms work for any convex distance function metric.},
  author = {Dickerson, Matthew T. and Drysdale, R.L. Scot and Sack, J̈{o}rg-Rüdiger},
  doi = {10.1142/S0218195992000147},
  issn = {0218-1959},
  journal = {International Journal of Computational Geometry \& Applications},
  keywords = {Algorithms,Delaunay triangulation,enumeration,nearest neighbors,selection},
  language = {en},
  month = {September},
  number = {03},
  pages = {221--239},
  publisher = {World Scientific Publishing Company},
  title = {{Simple Algorithms for Enumerating Interpoint Distances and Finding K Nearest Neighbors}},
  url = {http://www.worldscientific.com/doi/abs/10.1142/S0218195992000147},
  volume = {02},
  year = {1992}
}

Downloads: 0

{"_id":"E7Lb6wqnb6WWuFkmB","authorIDs":[],"author_short":["Dickerson, M.<nbsp>T.","Drysdale","Scot, R.","Sack, J.-"],"bibbaseid":"dickerson-drysdale-scot-sack-simplealgorithmsforenumeratinginterpointdistancesandfindingknearestneighbors-1992","bibdata":{"abstract":"We present an O(n log n+k log k) time and O(n+k) space algorithm which takes as input a set of n points in the plane and enumerates the k smallest distances between pairs of points in nondecreasing order. We also present an O(n log n+kn log k) solution to the problem of finding the k nearest neighbors for each of n points. Both algorithms are conceptually very simple, are easy to implement, and are based on a common data structure: the Delaunay triangulation. Variants of the algorithms work for any convex distance function metric.","author":["Dickerson, Matthew T.","Drysdale","Scot, R.L.","Sack, J̈org-Rüdiger"],"author_short":["Dickerson, M.<nbsp>T.","Drysdale","Scot, R.","Sack, J.-"],"bibtex":"@article{ DICKERSON1992,\n abstract = {We present an O(n log n+k log k) time and O(n+k) space algorithm which takes as input a set of n points in the plane and enumerates the k smallest distances between pairs of points in nondecreasing order. We also present an O(n log n+kn log k) solution to the problem of finding the k nearest neighbors for each of n points. Both algorithms are conceptually very simple, are easy to implement, and are based on a common data structure: the Delaunay triangulation. Variants of the algorithms work for any convex distance function metric.},\n author = {Dickerson, Matthew T. and Drysdale, R.L. Scot and Sack, J̈{o}rg-Rüdiger},\n doi = {10.1142/S0218195992000147},\n issn = {0218-1959},\n journal = {International Journal of Computational Geometry \\& Applications},\n keywords = {Algorithms,Delaunay triangulation,enumeration,nearest neighbors,selection},\n language = {en},\n month = {September},\n number = {03},\n pages = {221--239},\n publisher = {World Scientific Publishing Company},\n title = {{Simple Algorithms for Enumerating Interpoint Distances and Finding K Nearest Neighbors}},\n url = {http://www.worldscientific.com/doi/abs/10.1142/S0218195992000147},\n volume = {02},\n year = {1992}\n}","bibtype":"article","doi":"10.1142/S0218195992000147","id":"DICKERSON1992","issn":"0218-1959","journal":"International Journal of Computational Geometry \\& Applications","key":"DICKERSON1992","keywords":"Algorithms,Delaunay triangulation,enumeration,nearest neighbors,selection","language":"en","month":"September","number":"03","pages":"221--239","publisher":"World Scientific Publishing Company","title":"Simple Algorithms for Enumerating Interpoint Distances and Finding K Nearest Neighbors","type":"article","url":"http://www.worldscientific.com/doi/abs/10.1142/S0218195992000147","volume":"02","year":"1992","bibbaseid":"dickerson-drysdale-scot-sack-simplealgorithmsforenumeratinginterpointdistancesandfindingknearestneighbors-1992","role":"author","urls":{"Paper":"http://www.worldscientific.com/doi/abs/10.1142/S0218195992000147"},"keyword":["Algorithms","Delaunay triangulation","enumeration","nearest neighbors","selection"],"downloads":0,"html":""},"bibtype":"article","biburl":"http://www-ikn.ist.hokudai.ac.jp/~wasa/enum.bib","creationDate":"2015-04-23T04:51:44.874Z","downloads":0,"keywords":["algorithms","delaunay triangulation","enumeration","nearest neighbors","selection"],"search_terms":["simple","algorithms","enumerating","interpoint","distances","finding","nearest","neighbors","dickerson","drysdale","scot","sack"],"title":"Simple Algorithms for Enumerating Interpoint Distances and Finding K Nearest Neighbors","year":1992,"dataSources":["YRMeqhMHoNu9HzJoC"]}