{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,19]],"date-time":"2025-12-19T09:17:13Z","timestamp":1766135833310},"reference-count":11,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1991,9,1]],"date-time":"1991-09-01T00:00:00Z","timestamp":683683200000},"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":[[1991,9]]},"DOI":"10.1007\/bf02574695","type":"journal-article","created":{"date-parts":[[2007,3,22]],"date-time":"2007-03-22T14:31:20Z","timestamp":1174573880000},"page":"369-381","source":"Crossref","is-referenced-by-count":59,"title":["A sparse graph almost as good as the complete graph on points inK dimensions"],"prefix":"10.1007","volume":"6","author":[{"given":"Pravin M.","family":"Vaidya","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,6,26]]},"reference":[{"key":"BF02574695_CR1","doi-asserted-by":"crossref","unstructured":"P. Chew, There is a planar graph almost as good as the complete graph,Proc. 2nd Annual Symposium on Computational Geometry, 1986, pp 169\u2013177.","DOI":"10.1145\/10515.10534"},{"key":"BF02574695_CR2","doi-asserted-by":"crossref","unstructured":"K. L. Clarkson, Fast algorithms for the all-nearest-neighbors problem,Proc. 24th Annual Symposium on Foundations Computer Science, 1983, pp. 226\u2013232.","DOI":"10.1109\/SFCS.1983.16"},{"key":"BF02574695_CR3","doi-asserted-by":"crossref","unstructured":"K. L. Clarkson, Approximation algorithms for shortest path motion planning,Proc. 19th Annual ACM Symposium Theory of Computing, 1987, pp. 56\u201365.","DOI":"10.1145\/28395.28402"},{"key":"BF02574695_CR4","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1007\/BF02187801","volume":"5","author":"D. P. Dobkin","year":"1990","unstructured":"D. P. Dobkin, S. J. Friedman, and K. J. Supowit, Delaunay graphs are almost as good as complete graphs,Discrete Comput. Geom. 5 (1990), 399\u2013408.","journal-title":"Discrete Comput. Geom."},{"key":"BF02574695_CR5","unstructured":"T. Feder, Personal communication, 1989."},{"key":"BF02574695_CR6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF00288933","volume":"4","author":"R. A. Finkel","year":"1974","unstructured":"R. A. Finkel and J. L. Bentley, Quad-trees: a data structure for retrieval on composite keys,Acta Inform. 4 (1974), 1\u20139.","journal-title":"Acta Inform."},{"key":"BF02574695_CR7","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction","author":"F. P. Preparata","year":"1985","unstructured":"F. P. Preparata and M. I. Shamos,Computational Geometry: An Introduction, Springer-Verlag, New York, 1985."},{"key":"BF02574695_CR8","volume-title":"Combinatorial Algorithms: Theory and Practice","author":"E. M. Reingold","year":"1977","unstructured":"E. M. Reingold, J. Nievergelt, and N. Deo,Combinatorial Algorithms: Theory and Practice, Prentice Hall, Englewood Cliffs, NJ, 1977."},{"key":"BF02574695_CR9","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1007\/BF02187718","volume":"4","author":"P. M. Vaidya","year":"1989","unstructured":"P. M. Vaidya, AnO(n logn) algorithm for the all-nearest-neighbors problem,Discrete Comput. Geom. 4 (1989), 399\u2013408.","journal-title":"Discrete Comput. Geom."},{"key":"BF02574695_CR10","doi-asserted-by":"crossref","first-page":"569","DOI":"10.1007\/BF01553909","volume":"4","author":"P. M. Vaidya","year":"1989","unstructured":"P. M. Vaidya, Approximate minimum weight matching on points ink-dimensional space,Algorithmica,4 (1989), 569\u2013584.","journal-title":"Algorithmica"},{"key":"BF02574695_CR11","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1137\/0211059","volume":"11","author":"A. C. Yao","year":"1982","unstructured":"A. C. Yao, On construction minimum spanning trees ink-dimensional space and related problems,SIAM J. Comput. 11 (1982), 721\u2013736.","journal-title":"SIAM J. Comput."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02574695.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02574695\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02574695","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,18]],"date-time":"2019-05-18T16:30:33Z","timestamp":1558197033000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02574695"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,9]]},"references-count":11,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1991,9]]}},"alternative-id":["BF02574695"],"URL":"https:\/\/doi.org\/10.1007\/bf02574695","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,9]]}}}