{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T23:41:55Z","timestamp":1725493315632},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540662518"},{"type":"electronic","value":"9783540484813"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48481-7_32","type":"book-chapter","created":{"date-parts":[[2007,10,27]],"date-time":"2007-10-27T19:49:40Z","timestamp":1193514580000},"page":"366-377","source":"Crossref","is-referenced-by-count":2,"title":["On Computing the Diameter of a Point Set in High Dimensional Euclidean Space"],"prefix":"10.1007","author":[{"given":"Daniele V.","family":"Finocchiaro","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marco","family":"Pellegrini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,1,14]]},"reference":[{"key":"32_CR1","unstructured":"N. Alon and J. Spencer. The Probabilistic Method. Wiley, 1992."},{"key":"32_CR2","unstructured":"S. N. Bespamyatnikh. An efficient algorithm for the three-dimensional diameter problem. In Proc. 9th ACM-SIAM SODA, pages 137\u2013146, 1998."},{"issue":"36","key":"32_CR3","doi-asserted-by":"publisher","first-page":"929","DOI":"10.1145\/76359.76371","volume":"4","author":"A. Blumer","year":"1989","unstructured":"A. Blumer, A. Ehrenfeucht, D. Haussler, and M. Warmuth. Learnability and the Vapnik-Chervonenkis dimension. J. ACM, 4(36):929\u2013965, 1989.","journal-title":"J. ACM"},{"key":"32_CR4","doi-asserted-by":"crossref","unstructured":"A. Borodin, R. Ostrovsky, and Y. Rabani. Subquadratic approximation algorithms for clustering problems in high dimensional space. To appear in Proc. STOC, 1999.","DOI":"10.1145\/301250.301367"},{"key":"32_CR5","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/BF02573973","volume":"10","author":"B. Chazelle","year":"1993","unstructured":"B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir. Diameter, width, closest line pair, and parametric searching. Discrete Comput. Geom., 10:183\u2013196, 1993.","journal-title":"Discrete Comput. Geom."},{"key":"32_CR6","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"K. L. Clarkson","year":"1989","unstructured":"K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II. Discrete Comput. Geom., 4:387\u2013421, 1989.","journal-title":"Discrete Comput. Geom."},{"key":"32_CR7","doi-asserted-by":"crossref","unstructured":"D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progression. In Proc. 19th ACM STOC, pages 1\u20136, 1987.","DOI":"10.1145\/28395.28396"},{"key":"32_CR8","doi-asserted-by":"publisher","first-page":"899","DOI":"10.1214\/aop\/1176995384","volume":"6","author":"R. M. Dudley","year":"1978","unstructured":"R. M. Dudley. Central limit theorems for empirical measures. Annals of Probability, 6:899\u2013929, 1978.","journal-title":"Annals of Probability"},{"key":"32_CR9","doi-asserted-by":"crossref","unstructured":"R. M. Dudley. A Course on Empirical Processes. In Lecture Notes in Mathematics, No. 1097, pages 1\u2013142, 1984.","DOI":"10.1007\/BFb0099432"},{"key":"32_CR10","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0020-0190(89)90045-8","volume":"32","author":"E","year":"1989","unstructured":"\u00d6. Egecioglu and B. Kalantari. Approximating the diameter of a set of points in the Euclidean space. Information Processing Letters, 32:205\u2013211, 1989.","journal-title":"Information Processing Letters"},{"key":"32_CR11","doi-asserted-by":"publisher","first-page":"248","DOI":"10.2307\/2305092","volume":"53","author":"P. Erd\u00f6s","year":"1946","unstructured":"P. Erd\u00f6s. On sets of distances of n points. Amer. Math. Monthly, 53:248\u2013250, 1946.","journal-title":"Amer. Math. Monthly"},{"key":"32_CR12","first-page":"165","volume":"5","author":"P. Erd\u00f6s","year":"1960","unstructured":"P. Erd\u00f6s. On sets of distances of points in Euclidean spaces. Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl., 5:165\u2013169, 1960.","journal-title":"Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl."},{"issue":"9","key":"32_CR13","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1109\/2.410146","volume":"28","author":"M. Flickner","year":"1995","unstructured":"M. Flickner, H. Sawhney, W. Niblack, J. Ashley, Q. Huang, B. Dom, M. Gorkani, J. Hafner, D. Lee, D. Petkovic, D. Steele, and P. Yanker. Query by image and video content: The QBIC system. Computer, 28(9):23\u201332, 1995.","journal-title":"Computer"},{"issue":"44","key":"32_CR14","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1016\/0095-8956(88)90043-3","volume":"B","author":"P. Frankl","year":"1988","unstructured":"P. Frankl and H. Maehara. The Johnson-Lindenstrauss lemma and the sphericity of some graphs. Journal of Combinatorial Theory, Series B 44:355\u2013362, 1988.","journal-title":"Journal of Combinatorial Theory"},{"key":"32_CR15","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/BF02187841","volume":"7","author":"P. Gritzmann","year":"1992","unstructured":"P. Gritzmann and V. Klee. Inner and outer j-radii of convex bodies in finite dimensional normed spaces. Discrete Computat. Geom., 7:255\u2013280, 1992.","journal-title":"Discrete Computat. Geom."},{"key":"32_CR16","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/BF01581243","volume":"59","author":"P. Gritzmann","year":"1993","unstructured":"P. Gritzmann and V. Klee. Computational complexity of inner and outer j-radii of polytopes in finite-dimensional normed spaces. Mathematical programming, 59:163\u2013213, 1993.","journal-title":"Mathematical programming"},{"key":"32_CR17","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/0012-365X(94)00111-U","volume":"136","author":"P. Gritzmann","year":"1994","unstructured":"P. Gritzmann and V. Klee. On the complexity of some basic problems in computational convexity: I. Containment problems. Discrete Math., 136:129\u2013174, 1994.","journal-title":"Discrete Math."},{"issue":"9","key":"32_CR18","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1109\/2.410145","volume":"28","author":"V. N. Gudivada","year":"1995","unstructured":"V. N. Gudivada and V. V. Raghavan. Guest editors\u2019 introduction: Content-based image retrieval systems. Computer, 28(9):18\u201322, 1995.","journal-title":"Computer"},{"key":"32_CR19","doi-asserted-by":"crossref","unstructured":"C. E. Jacobs, A. Finkelstein, and D. H. Salesin. Fast multiresolution image querying. In Robert Cook, editor, SIGGRAPH 95 Conference Proceedings, pages 277\u2013286. AddisonWesley, August 1995.","DOI":"10.1145\/218380.218454"},{"key":"32_CR20","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1090\/conm\/026\/737400","volume":"26","author":"W. B. Johnson","year":"1984","unstructured":"W. B. Johnson and J. Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. In Conference in Modern Analysis and Probability, volume 26 of Contemporary Mathematics, pages 189\u2013206, 1984.","journal-title":"Conference in Modern Analysis and Probability"},{"key":"32_CR21","doi-asserted-by":"crossref","unstructured":"J. M. Kleinberg. Two algorithms for nearest-neighbor search in high dimensions. In 29th ACM STOC, pages 599\u2013608, 1997.","DOI":"10.1145\/258533.258653"},{"key":"32_CR22","unstructured":"D. E. Knuth. Seminumerical Algorithms, volume 2 of The Art of Computer Programming. Addison-Wesley, 2nd edition, 1981."},{"key":"32_CR23","doi-asserted-by":"crossref","unstructured":"J. Matou\u0161ek and O. Schwarzkopf. A deterministic algorithm for the three-dimensional diameter problem. In Proc. 25th STOC, pages 478\u2013484, 1993.","DOI":"10.1145\/167088.167217"},{"key":"32_CR24","doi-asserted-by":"crossref","unstructured":"R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.","DOI":"10.1017\/CBO9780511814075"},{"key":"32_CR25","unstructured":"K. Mulmuley. Computational Geometry. An Introduction Through Randomized Algorithms. Prentice Hall, 1994."},{"key":"32_CR26","doi-asserted-by":"crossref","unstructured":"F. P. Preparata and M. I. Shamos. Computational Geometry: an Introduction. SpringerVerlag, 1985.","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"32_CR27","doi-asserted-by":"crossref","unstructured":"E. A. Ramos. Construction of 1-d lower envelopes and applications. In Proc. 13th Annual Symp. on Computational Geometry, pages 57\u201366, 1997.","DOI":"10.1145\/262839.262864"},{"key":"32_CR28","first-page":"39","volume":"5","author":"S. Straszewicz","year":"1957","unstructured":"S. Straszewicz. Sur un probl\u00e9me g\u00e9ometrique de P. Erd\u00f6s. Bull. Acad. Polon. Sci. Cl. III, 5:39\u201340, 1957.","journal-title":"Bull. Acad. Polon. Sci. Cl. III"},{"key":"32_CR29","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"V. N. Vapnik","year":"1971","unstructured":"V. N. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory Prob. Appl., 16:264\u2013280, 1971.","journal-title":"Theory Prob. Appl."},{"key":"32_CR30","unstructured":"M. Vidyasagar. Learning and generalization with applications to neural networks. Preliminary version of [31], November 1995."},{"key":"32_CR31","volume-title":"A Theory of Learning and Generalization: with Applications to Neural Networks and Control System","author":"M. Vidyasagar","year":"1997","unstructured":"M. Vidyasagar. A Theory of Learning and Generalization: with Applications to Neural Networks and Control System. Springer-Verlag, London, 1997."},{"key":"32_CR32","unstructured":"A. C. Yao. Personal communication. Also in \u201cOn computing the distance matrix of n points in k dimensions\u201d, TR IBM San Jose Research Center, about 1982."},{"issue":"4","key":"32_CR33","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1137\/0211059","volume":"11","author":"A. C. Yao","year":"1982","unstructured":"A. C. Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM Journal of Computing, 11(4):721\u2013736, 1982.","journal-title":"SIAM Journal of Computing"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA\u2019 99"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48481-7_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T22:21:04Z","timestamp":1556922064000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48481-7_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540662518","9783540484813"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/3-540-48481-7_32","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]}}}