{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T16:05:52Z","timestamp":1725552352208},"publisher-location":"Berlin, Heidelberg","reference-count":39,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642131929"},{"type":"electronic","value":"9783642131936"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-13193-6_41","type":"book-chapter","created":{"date-parts":[[2010,4,27]],"date-time":"2010-04-27T07:54:59Z","timestamp":1272354899000},"page":"486-500","source":"Crossref","is-referenced-by-count":5,"title":["Geometric Minimum Spanning Trees with GeoFilterKruskal"],"prefix":"10.1007","author":[{"given":"Samidh","family":"Chatterjee","sequence":"first","affiliation":[]},{"given":"Michael","family":"Connor","sequence":"additional","affiliation":[]},{"given":"Piyush","family":"Kumar","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"5","key":"41_CR1","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1007\/BF02574698","volume":"6","author":"P.K. Agarwal","year":"1991","unstructured":"Agarwal, P.K., Edelsbrunner, H., Schwarzkopf, O., Welzl, E.: Euclidean minimum spanning trees and bichromatic closest pairs. Discrete Comput. Geom.\u00a06(5), 407\u2013422 (1991)","journal-title":"Discrete Comput. Geom."},{"issue":"5","key":"41_CR2","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S.: Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. J. ACM\u00a045(5), 753\u2013782 (1998)","journal-title":"J. ACM"},{"issue":"6","key":"41_CR3","doi-asserted-by":"publisher","first-page":"891","DOI":"10.1145\/293347.293348","volume":"45","author":"S. Arya","year":"1998","unstructured":"Arya, S., Mount, D.M., Netanyahu, N.S., Silverman, R., Wu, A.Y.: An optimal algorithm for approximate nearest neighbor searching fixed dimensions. J. ACM\u00a045(6), 891\u2013923 (1998)","journal-title":"J. ACM"},{"key":"41_CR4","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1093\/mnras\/216.1.17","volume":"216","author":"J.D. Barrow","year":"1985","unstructured":"Barrow, J.D., Bhavsar, S.P., Sonoda, D.H.: Minimal spanning trees, filaments and galaxy clustering. MNRAS\u00a0216, 17\u201335 (1985)","journal-title":"MNRAS"},{"issue":"4","key":"41_CR5","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1145\/355921.355927","volume":"6","author":"J.L. Bentley","year":"1980","unstructured":"Bentley, J.L., Weide, B.W., Yao, A.C.: Optimal expected-time algorithms for closest point problems. ACM Trans. Math. Softw.\u00a06(4), 563\u2013580 (1980)","journal-title":"ACM Trans. Math. Softw."},{"key":"41_CR6","doi-asserted-by":"crossref","first-page":"1461","DOI":"10.1093\/mnras\/282.4.1461","volume":"282","author":"S.P. Bhavsar","year":"1996","unstructured":"Bhavsar, S.P., Splinter, R.J.: The superiority of the minimal spanning tree in percolation analyses of cosmological data sets. MNRAS\u00a0282, 1461\u20131466 (1996)","journal-title":"MNRAS"},{"issue":"3","key":"41_CR7","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1016\/0167-6377(82)90010-4","volume":"1","author":"J.J. Brennan","year":"1982","unstructured":"Brennan, J.J.: Minimal spanning trees and partial sorting. Operations Research Letters\u00a01(3), 138\u2013141 (1982)","journal-title":"Operations Research Letters"},{"unstructured":"Paul, B.: Callahan. Dealing with higher dimensions: the well-separated pair decomposition and its applications. PhD thesis, Johns Hopkins University, Baltimore, MD, USA (1995)","key":"41_CR8"},{"unstructured":"Chan, T.M.: Manuscript: A minimalist\u2019s implementation of an approximate nearest n eighbor algorithm in fixed dimensions (2006)","key":"41_CR9"},{"issue":"5","key":"41_CR10","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1016\/j.ipl.2008.02.008","volume":"107","author":"T.M. Chan","year":"2008","unstructured":"Chan, T.M.: Well-separated pair decomposition in linear time? Inf. Process. Lett.\u00a0107(5), 138\u2013141 (2008)","journal-title":"Inf. Process. Lett."},{"key":"41_CR11","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/BF01553902","volume":"4","author":"K.L. Clarkson","year":"1989","unstructured":"Clarkson, K.L.: An algorithm for geometric minimum spanning trees requiring nearly linear expected time. Algorithmica\u00a04, 461\u2013469 (1989); Included in PhD Thesis","journal-title":"Algorithmica"},{"unstructured":"Connor, M., Kumar, P.: Stann library, \n                    \n                      http:\/\/www.compgeom.com\/~stann\/","key":"41_CR12"},{"unstructured":"Connor, M., Kumar, P.: Parallel construction of k-nearest neighbor graphs for point clouds. In: Proceedings of Volume and Point-Based Graphics, August 2008, pp. 25???32. IEEE VGTC (2008);","key":"#cr-split#-41_CR13.1"},{"unstructured":"Accepted to IEEE Transactions on Visualization and Computer Graphics (2009)","key":"#cr-split#-41_CR13.2"},{"unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press\/McGraw-Hill (2001)","key":"41_CR14"},{"issue":"1","key":"41_CR15","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1109\/99.660313","volume":"5","author":"L. Dagum","year":"1998","unstructured":"Dagum, L., Menon, R.: Openmp: an industry standard api for shared-memory programming. IEEE Computational Science and Engineering\u00a05(1), 46\u201355 (1998)","journal-title":"IEEE Computational Science and Engineering"},{"key":"41_CR16","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1145\/73833.73869","volume-title":"SCG 1989: Proceedings of the fifth annual symposium on Computational geometry","author":"R.A. Dwyer","year":"1989","unstructured":"Dwyer, R.A.: Higher-dimensional voronoi diagrams in linear expected time. In: SCG 1989: Proceedings of the fifth annual symposium on Computational geometry, pp. 326\u2013333. ACM, New York (1989)"},{"unstructured":"Erickson, J.: On the relative complexities of some geometric problems. In: Proc. 7th Canad. Conf. Comput. Geom., pp. 85\u201390 (1995)","key":"41_CR17"},{"unstructured":"Erickson, J.G.: Lower bounds for fundamental geometric problems. PhD thesis, University of California, Berkeley, Chair-Seidel, Raimund (1996)","key":"41_CR18"},{"key":"41_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/978-3-540-75520-3_19","volume-title":"Algorithms \u2013 ESA 2007","author":"G. Franceschini","year":"2007","unstructured":"Franceschini, G., Muthukrishnan, S.M., P\u01cetra\u015fcu, M.: Radix sorting with no extra space. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol.\u00a04698, pp. 194\u2013205. Springer, Heidelberg (2007)"},{"key":"41_CR20","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1145\/800057.808675","volume-title":"STOC 1984: Proceedings of the sixteenth annual ACM symposium on Theory of computing","author":"H.N. Gabow","year":"1984","unstructured":"Gabow, H.N., Bentley, J.L., Tarjan, R.E.: Scaling and related techniques for geometry problems. In: STOC 1984: Proceedings of the sixteenth annual ACM symposium on Theory of computing, pp. 135\u2013143. ACM, New York (1984)"},{"unstructured":"Morton, G.M.: A computer oriented geodetic data base; and a new technique in file sequencing. Technical report, IBM Ltd., Ottawa, Canada (1966)","key":"41_CR21"},{"key":"41_CR22","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1145\/201019.201022","volume":"42","author":"D.R. Karger","year":"1995","unstructured":"Karger, D.R., Klein, P.N., Tarjan, R.E.: A randomized linear-time algorithm to find minimum spanning trees. Journal of the ACM\u00a042, 321\u2013328 (1995)","journal-title":"Journal of the ACM"},{"key":"41_CR23","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1145\/195058.195084","volume-title":"STOC 1994: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing","author":"P.N. Klein","year":"1994","unstructured":"Klein, P.N., Tarjan, R.E.: A randomized linear-time algorithm for finding minimum spanning trees. In: STOC 1994: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, pp. 9\u201315. ACM, New York (1994)"},{"doi-asserted-by":"crossref","unstructured":"Kruskal, J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. In: Proc. American Math. Society, pp. 7\u201348 (1956)","key":"41_CR24","DOI":"10.1090\/S0002-9939-1956-0078686-7"},{"issue":"4","key":"41_CR25","first-page":"446","volume":"6","author":"D. Krznaric","year":"1999","unstructured":"Krznaric, D., Levcopoulos, C., Nilsson, B.J.: Minimum spanning trees in d dimensions. Nordic J. of Computing\u00a06(4), 446\u2013461 (1999)","journal-title":"Nordic J. of Computing"},{"key":"41_CR26","doi-asserted-by":"crossref","DOI":"10.1201\/b10626","volume-title":"Geometric Data Structures for Computer Graphics","author":"E. Langetepe","year":"2006","unstructured":"Langetepe, E., Zachmann, G.: Geometric Data Structures for Computer Graphics. A. K. Peters, Ltd., Natick (2006)"},{"unstructured":"March, W., Gray, A.: Large-scale euclidean mst and hierarchical clustering. In: Workshop on Efficient Machine Learning (2007)","key":"41_CR27"},{"key":"41_CR28","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1111\/j.1467-8659.1995.cgf143_0445.x","volume":"14","author":"R. Mencl","year":"2008","unstructured":"Mencl, R.: A graph based approach to surface reconstruction. Computer Graphics Forum\u00a014, 445\u2013456 (2008)","journal-title":"Computer Graphics Forum"},{"key":"41_CR29","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and Computing: Randomized Algorithms and Probabilistic Analysis","author":"M. Mitzenmacher","year":"2005","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, New York (2005)"},{"issue":"1","key":"41_CR30","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1145\/234313.234327","volume":"28","author":"R. Motwani","year":"1996","unstructured":"Motwani, R., Raghavan, P.: Randomized algorithms. ACM Comput. Surv.\u00a028(1), 33\u201337 (1996)","journal-title":"ACM Comput. Surv."},{"key":"41_CR31","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1145\/945394.945400","volume":"6","author":"G. Narasimhan","year":"2001","unstructured":"Narasimhan, G., Zachariasen, M.: Geometric minimum spanning trees via well-separated pair decompositions. J. Exp. Algorithmics\u00a06, 6 (2001)","journal-title":"J. Exp. Algorithmics"},{"key":"41_CR32","first-page":"52","volume-title":"ALENEX","author":"V. Osipov","year":"2009","unstructured":"Osipov, V., Sanders, P., Singler, J.: The filter-kruskal minimum spanning tree algorithm. In: Finocchi, I., Hershberger, J. (eds.) ALENEX, pp. 52\u201361. SIAM, Philadelphia (2009)"},{"key":"41_CR33","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":"Preparata, F.P., Shamos, M.I.: Computational geometry: an introduction. Springer, New York (1985)"},{"key":"41_CR34","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1145\/1229428.1229458","volume-title":"PPoPP 2007: Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming","author":"F. Putze","year":"2007","unstructured":"Putze, F., Sanders, P., Singler, J.: Mcstl: the multi-core standard template library. In: PPoPP 2007: Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming, pp. 144\u2013145. ACM, New York (2007)"},{"doi-asserted-by":"crossref","unstructured":"Rajasekaran, S.: On the euclidean minimum spanning tree problem. Computing Letters\u00a01(1) (2004)","key":"41_CR35","DOI":"10.1163\/1574040053326325"},{"key":"41_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/BFb0014497","volume-title":"Applied Computational Geometry. Towards Geometric Engineering","author":"J.R. Shewchuk","year":"1996","unstructured":"Shewchuk, J.R.: Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator. In: Lin, M.C., Manocha, D. (eds.) FCRC-WS 1996 and WACG 1996. LNCS, vol.\u00a01148, pp. 203\u2013222. Springer, Heidelberg (1996); From the First ACM Workshop on Applied Computational Geometry"},{"issue":"3","key":"41_CR37","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/0020-0190(93)90019-6","volume":"45","author":"F. Suraweera","year":"1993","unstructured":"Suraweera, F., Bhattacharya, P.: An o(log m) parallel algorithm for the minimum spanning tree problem. Inf. Process. Lett.\u00a045(3), 159\u2013163 (1993)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"41_CR38","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1109\/T-C.1971.223083","volume":"C-20","author":"C.T. Zahn","year":"1971","unstructured":"Zahn, C.T.: Graph-theoretical methods for detecting and describing gestalt clusters. Transactions on Computers\u00a0C-20(1), 68\u201386 (1971)","journal-title":"Transactions on Computers"}],"container-title":["Lecture Notes in Computer Science","Experimental Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-13193-6_41.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T07:57:20Z","timestamp":1619769440000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-13193-6_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642131929","9783642131936"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-13193-6_41","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}