{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,9]],"date-time":"2026-07-09T14:29:31Z","timestamp":1783607371203,"version":"3.55.0"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1997,4,1]],"date-time":"1997-04-01T00:00:00Z","timestamp":859852800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[1997,4]]},"DOI":"10.1007\/pl00009293","type":"journal-article","created":{"date-parts":[[2006,2,17]],"date-time":"2006-02-17T12:36:03Z","timestamp":1140179763000},"page":"263-282","source":"Crossref","is-referenced-by-count":177,"title":["On Nearest-Neighbor Graphs"],"prefix":"10.1007","volume":"17","author":[{"given":"D.","family":"Eppstein","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"M. S.","family":"Paterson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"F. F.","family":"Yao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"170300263_CR1","volume-title":"The Probabilistic Method","author":"N. Alon","year":"1992","unstructured":"N. Alon and J. H. Spencer. The Probabilistic Method. Wiley-Interscience, New York, 1992."},{"key":"170300263_CR2","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/BF01762114","volume":"3","author":"M. Bern","year":"1988","unstructured":"M. Bern. Two probabilistic results on rectilinear Steiner trees. Algorithmica 3 (1988), 191\u2013204.","journal-title":"Algorithmica"},{"key":"170300263_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0021-9991(86)90050-1","volume":"66","author":"J. Boris","year":"1986","unstructured":"J. Boris. A vectorized \u201cnear neighbors\u201d algorithm of order N using a monotonic logical grid. Journal of Computational Physics 66 (1986), 1\u201320.","journal-title":"Journal of Computational Physics"},{"key":"170300263_CR4","doi-asserted-by":"crossref","unstructured":"P. B. Callahan. Optimal parallel all-nearest-neighbors using the well-separated pair decomposition. Proc. 34 th IEEE Symp. on Foundations of Computer Science (1993), pp. 332\u2013340.","DOI":"10.1109\/SFCS.1993.366854"},{"key":"170300263_CR5","doi-asserted-by":"crossref","unstructured":"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. Proc. 24th ACM Symp. on Theory of Computing (1992), pp. 546\u2013556.","DOI":"10.1145\/129712.129766"},{"key":"170300263_CR6","doi-asserted-by":"crossref","unstructured":"K. L. Clarkson. Fast algorithms for the all-nearest-neighbors problem. Proc. 24th IEEE Symp. on Foundations of Computer Science (1983), pp. 226\u2013232.","DOI":"10.1109\/SFCS.1983.16"},{"key":"170300263_CR7","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2016-7","volume-title":"Sphere Packings, Lattices and Groups","author":"J. H. Conway","year":"1988","unstructured":"J. H. Conway and N. J. A. Sloane. Sphere Packings, Lattices and Groups. Springer-Verlag, New York, 1988."},{"key":"170300263_CR8","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0898-1221(88)90071-5","volume":"15","author":"L. Devroye","year":"1988","unstructured":"L. Devroye. The expected size of some graphs in computational geometry. Computers & Mathematics with Applications 15 (1988), 53\u201364.","journal-title":"Computers & Mathematics with Applications"},{"key":"170300263_CR9","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/0925-7721(95)00009-7","volume":"5","author":"M. T. Dickerson","year":"1996","unstructured":"M. T. Dickerson and D. Eppstein. Algorithms for proximity problems in higher dimensions. Computational Geometry, Theory & Applications 5 (1996), 277\u2013291.","journal-title":"Computational Geometry, Theory & Applications"},{"key":"170300263_CR10","doi-asserted-by":"crossref","unstructured":"P. Eades and S. Whitesides. The realization problem for Euclidean minimum spanning trees is NP-hard. Proc. 10th ACM Symp. on Computational Geometry (1994), pp. 49\u201356.","DOI":"10.1145\/177424.177507"},{"key":"170300263_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms in Combinatorial Geometry","author":"H. Edelsbrunner","year":"1987","unstructured":"H. Edelsbrunner. Algorithms in Combinatorial Geometry. Springer-Verlag, New York, 1987."},{"key":"170300263_CR12","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/BF02574012","volume":"11","author":"D. Eppstein","year":"1994","unstructured":"D. Eppstein and J. Erickson. Iterated nearest neighbors and finding minimal polytopes. Discrete & Computational Geometry 11 (1994), 321\u2013350.","journal-title":"Discrete & Computational Geometry"},{"key":"170300263_CR13","unstructured":"C. Monma and S. Suri. Transitions in geometric spanning trees. Proc. 7th ACM Symp. on Computational Geometry (1991), pp. 239\u2013249."},{"key":"170300263_CR14","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1007\/3-540-55719-9_93","volume-title":"Proc. 19th Internat. Coll. on Automata, Languages and Programming. LNCS, 623","author":"M. S. Paterson","year":"1992","unstructured":"M. S. Paterson and F. F. Yao. On nearest-neighbor graphs. Proc. 19th Internat. Coll. on Automata, Languages and Programming. LNCS, 623. Springer-Verlag, Berlin, 1992, pp. 416\u2013426."},{"key":"170300263_CR15","unstructured":"S.-H. Teng and F. F. Yao. Percolation and k-nearest neighbor clustering. Manuscript, 1993."},{"key":"170300263_CR16","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/BF02187718","volume":"4","author":"P. Vaidya","year":"1989","unstructured":"P. Vaidya. An O(n log n) algorithm for the all-nearest-neighbors problem. Discrete & Computational Geometry 4 (1989), 101\u2013115.","journal-title":"Discrete & Computational Geometry"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/PL00009293.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/PL00009293\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/PL00009293","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T09:20:46Z","timestamp":1558516846000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/PL00009293"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,4]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1997,4]]}},"alternative-id":["170300263"],"URL":"https:\/\/doi.org\/10.1007\/pl00009293","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,4]]}}}