{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,10]],"date-time":"2026-11-10T18:54:43Z","timestamp":1794336883188,"version":"4.9.0"},"publisher-location":"Berlin\/Heidelberg","reference-count":22,"publisher":"Springer-Verlag","isbn-type":[{"value":"3540543430","type":"print"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0028254","type":"book-chapter","created":{"date-parts":[[2005,11,22]],"date-time":"2005-11-22T00:52:14Z","timestamp":1132620734000},"page":"105-116","source":"Crossref","is-referenced-by-count":3,"title":["Farthest neighbors, maximum spanning trees and related problems in higher dimensions"],"prefix":"10.1007","author":[{"given":"Pankaj K.","family":"Agarwal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ji\u0159\u00ed","family":"Matou\u0161ek","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Subhash","family":"Suri","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"11_CR1","doi-asserted-by":"crossref","unstructured":"P. Agarwal, H. Edelsbrunner, O. Schwarzkopf, and E. Welzl. Euclidean minimum spanning trees and bichromatic closest pairs. Proc. of 6th ACM Symp. on Computational Geometry, 1990, pp. 203\u2013210.","DOI":"10.1145\/98524.98567"},{"key":"11_CR2","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/0196-6774(88)90035-1","volume":"9","author":"F. Aurenhammer","year":"1988","unstructured":"F. Aurenhammer. Improved algorithms for discs and balls using power diagrams. Journal of Algorithms, 9 (1988), 151\u2013161.","journal-title":"Journal of Algorithms"},{"key":"11_CR3","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/S0019-9958(85)80045-0","volume":"64","author":"B. Chazelle","year":"1985","unstructured":"B. Chazelle. How to search in history. Information and Control, 64 (1985), 77\u201399.","journal-title":"Information and Control"},{"key":"11_CR4","doi-asserted-by":"crossref","unstructured":"K. Clarkson. Fast expected-time and approximate algorithms for geometric minimum spanning tree. Proc. 16th Annual Symposium on Theory of Computing, 1984, pp. 342\u2013348.","DOI":"10.1145\/800057.808699"},{"key":"11_CR5","doi-asserted-by":"crossref","first-page":"830","DOI":"10.1137\/0217052","volume":"17","author":"K. Clarkson","year":"1988","unstructured":"K. Clarkson. A randomized algorithm for closest-point queries. SIAM J. Computing, 17 (1988), 830\u2013847.","journal-title":"SIAM J. Computing"},{"key":"11_CR6","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"K. Clarkson","year":"1989","unstructured":"K. Clarkson and P. Shor. Applications of random sampling in computational geometry, II. Discrete and Computational Geometry. 4 (1989), pp. 387\u2013421.","journal-title":"Discrete and Computational Geometry"},{"key":"11_CR7","doi-asserted-by":"crossref","unstructured":"H. Edelsbrunner. An acyclicity theorem for cell complexes in d dimensions. Proc. of 5th ACM Symp. on Computational Geometry, 1989, pp. 145\u2013151.","DOI":"10.1145\/73833.73850"},{"key":"11_CR8","doi-asserted-by":"crossref","unstructured":"H. Edelsbrunner. Algorithms in Combinatorial Geometry, Springer-Verlag, 1987.","DOI":"10.1007\/978-3-642-61568-9"},{"key":"11_CR9","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/BF02187681","volume":"1","author":"H. Edelsbrunner","year":"1985","unstructured":"H. Edelsbrunner and R. Seidel. Voronoi diagrams and arrangements. Discrete and Computational Geometry, 1 (1985), 25\u201344.","journal-title":"Discrete and Computational Geometry"},{"key":"11_CR10","doi-asserted-by":"crossref","unstructured":"H. Edelsbrunner and M. Sharir, A hyperplane incidence problem with applications to counting distances. Proc. of International Symposium on Algorithms, LNCS 450, Springer-Verlag, 1990.","DOI":"10.1007\/3-540-52921-7_91"},{"key":"11_CR11","doi-asserted-by":"crossref","unstructured":"O. Egecioglu and B. Kalantari. Approximating the diameter of a set of points in the Euclidean space. Technical report, Rutgers University, 1989.","DOI":"10.1016\/0020-0190(89)90045-8"},{"key":"11_CR12","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0022-0000(85)90014-5","volume":"30","author":"H. N. Gabow","year":"1985","unstructured":"H. N. Gabow and R. E. Tarjan. A linear-time algorithm for a special case of disjoint set union. Journal of Computer and System Sciences, 30 (1985), 209\u2013221.","journal-title":"Journal of Computer and System Sciences"},{"key":"11_CR13","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1109\/MAHC.1985.10011","volume":"7","author":"R. L. Graham","year":"1985","unstructured":"R. L. Graham and P. Hell. On the history of minimum spanning tree problem. Annals of History of Computing, 7 (1985), 43\u201357.","journal-title":"Annals of History of Computing"},{"key":"11_CR14","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D. Haussler","year":"1987","unstructured":"D. Haussler and E. Welzl. \u2208-nets and simplex range queries, Discrete and Computational Geometry. 2 (1987), 127\u2013151.","journal-title":"Discrete and Computational Geometry"},{"key":"11_CR15","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1007\/BF01840396","volume":"5","author":"C. Monma","year":"1990","unstructured":"C. Monma, M. Paterson, S. Suri and F. F. Yao. Computing Euclidean maximum spanning trees. Algorithmica, 5 (1990), 407\u2013419.","journal-title":"Algorithmica"},{"key":"11_CR16","unstructured":"C. Monma and S. Suri. Partitioning points and graphs to minimize the maximum or the sum of diameters. Proceedings of 6th International Conference on the Theory and Applications of Graphs, John Wiley and Sons, 1989"},{"key":"11_CR17","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry","author":"F. P. Preparata","year":"1985","unstructured":"F. P. Preparata and M. I. Shamos. Computational Geometry. Springer Verlag, New York, 1985."},{"key":"11_CR18","first-page":"3","volume":"382","author":"F. Preparata","year":"1989","unstructured":"F. Preparata and R. Tamassia. Efficient spatial point location. Workshop on Algorithms and Data Structures, LNCS 382, Springer-Verlag, (1989), 3\u201311.","journal-title":"LNCS"},{"key":"11_CR19","volume-title":"A convex hull algorithm optimal for point sets in even dimensions","author":"R. Seidel","year":"1981","unstructured":"R. Seidel. A convex hull algorithm optimal for point sets in even dimensions. University of British Columbia, Vancouver, 1981."},{"key":"11_CR20","doi-asserted-by":"crossref","first-page":"572","DOI":"10.1137\/0217035","volume":"17","author":"P. Vaidya","year":"1988","unstructured":"P. Vaidya. Minimum spanning trees in k-dimensional space. SIAM J. of Computing, 17 (1988), 572\u2013582.","journal-title":"SIAM J. of Computing"},{"key":"11_CR21","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-neighbor problem. Discrete and Computational Geometry, 4 (1989), 101\u2013115.","journal-title":"Discrete and Computational Geometry"},{"key":"11_CR22","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1137\/0211059","volume":"11","author":"A. Yao","year":"1982","unstructured":"A. Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems, SIAM J. Computing, 11 (1982), 721\u2013736.","journal-title":"SIAM J. Computing"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0028254.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T16:58:32Z","timestamp":1607533112000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0028254"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540543430"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/bfb0028254","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/bfb0028243","asserted-by":"object"}]},"subject":[]}}