{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T00:00:20Z","timestamp":1773273620374,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540388753","type":"print"},{"value":"9783540388760","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11841036_17","type":"book-chapter","created":{"date-parts":[[2006,9,11]],"date-time":"2006-09-11T09:20:54Z","timestamp":1157966454000},"page":"160-171","source":"Crossref","is-referenced-by-count":23,"title":["Necklaces, Convolutions, and X + Y"],"prefix":"10.1007","author":[{"given":"David","family":"Bremner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Timothy M.","family":"Chan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erik D.","family":"Demaine","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeff","family":"Erickson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ferran","family":"Hurtado","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John","family":"Iacono","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Langerman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Perouz","family":"Taslakian","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"17_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/11534273_36","volume-title":"Algorithms and Data Structures","author":"I. Baran","year":"2005","unstructured":"Baran, I., Demaine, E.D., P\u01cetra\u015fcu, M.: Subquadratic algorithms for 3SUM. In: Dehne, F., L\u00f3pez-Ortiz, A., Sack, J.-R. (eds.) WADS 2005. LNCS, vol.\u00a03608, pp. 409\u2013421. Springer, Heidelberg (2005)"},{"issue":"3","key":"17_CR2","first-page":"550","volume":"10","author":"R. Bellman","year":"1962","unstructured":"Bellman, R., Karush, W.: Mathematical programming and the maximum transform. J. SIAM\u00a010(3), 550\u2013567 (1962)","journal-title":"J. SIAM"},{"key":"17_CR3","unstructured":"Bernstein, D.J.: Fast multiplication and its applications. In: Buhler, J., Stevenhagen, P. (eds.) Algorithmic Number Theory. Cambridge University Press, Cambridge (to appear)"},{"issue":"3","key":"17_CR4","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0167-6377(94)90048-5","volume":"15","author":"M. Bussieck","year":"1994","unstructured":"Bussieck, M., Hassler, H., Woeginger, G.J., Zimmermann, U.T.: Fast algorithms for the maximum convolution problem. Oper. Res. Lett.\u00a015(3), 133\u2013141 (1994)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"17_CR5","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1007\/s00224-005-1239-x","volume":"39","author":"J. Cardinal","year":"2006","unstructured":"Cardinal, J., Kremer, S., Langerman, S.: Juggling with pattern matching. Theory Comput. Syst.\u00a039(3), 425\u2013437 (2006)","journal-title":"Theory Comput. Syst."},{"key":"17_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1007\/11534273_28","volume-title":"Algorithms and Data Structures","author":"T.M. Chan","year":"2005","unstructured":"Chan, T.M.: All-pairs shortest paths with real weights in O(n\n                           3\/logn) time. In: Dehne, F., L\u00f3pez-Ortiz, A., Sack, J.-R. (eds.) WADS 2005. LNCS, vol.\u00a03608, pp. 318\u2013324. Springer, Heidelberg (2005)"},{"key":"17_CR7","doi-asserted-by":"crossref","unstructured":"Cohn, H., Kleinberg, R., Szegedy, B., Umans, C.: Group-theoretic algorithms for matrix multiplication. In: Proc. 46th IEEE Symp. Found. Computer Science, pp.\u00a0379\u2013388 (2005)","DOI":"10.1109\/SFCS.2005.39"},{"issue":"4","key":"17_CR8","doi-asserted-by":"publisher","first-page":"979","DOI":"10.1089\/cmb.2006.13.979","volume":"13","author":"J. Colannino","year":"2006","unstructured":"Colannino, J., Damian, M., Hurtado, F., Iacono, J., Meijer, H., Ramaswami, S., Toussaint, G.: An O(n logn)-time algorithm for the restriction scaffold assignment. J. Comput. Biol.\u00a013(4), 979\u2013989 (2006)","journal-title":"J. Comput. Biol."},{"key":"17_CR9","doi-asserted-by":"crossref","unstructured":"Cole, R., Hariharan, R.: Verifying candidate matches in sparse and wildcard matching. In: Proc. 34th ACM Symp. Theory of Computing, pp.\u00a0592\u2013601 (2002)","DOI":"10.1145\/509907.509992"},{"key":"17_CR10","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1090\/S0025-5718-1965-0178586-1","volume":"19","author":"J.W. Cooley","year":"1965","unstructured":"Cooley, J.W., Tukey, J.W.: An algorithm for the machine calculation of complex Fourier series. Math. Comp.\u00a019, 297\u2013301 (1965)","journal-title":"Math. Comp."},{"key":"17_CR11","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)","edition":"2"},{"key":"17_CR12","unstructured":"Demaine, E.D., Mitchell, J.S.B., O\u2019Rourke, J.: Problem 41: Sorting X + Y (pairwise sums). In: The Open Problems Project, \n                    \n                      http:\/\/cs.smith.edu\/~orourke\/TOPP\/P41.html"},{"key":"17_CR13","unstructured":"Demaine, E.D., O\u2019Rourke, J.: Open problems from CCCG 2005. In: Proc. 18th Canadian Conference on Computational Geometry (2006)"},{"key":"17_CR14","unstructured":"D\u00edaz-B\u00e1\u00f1ez, J.M., Farigu, G., G\u00f3mez, F., Rappaport, D., Toussaint, G.T.: El comp\u00e1s flamenco: A phylogenetic analysis. In: Proc. BRIDGES: Mathematical Connections in Art, Music, and Science, pp. 61\u201370 (2004)"},{"key":"17_CR15","doi-asserted-by":"crossref","unstructured":"Erickson, J.: Lower bounds for linear satisfiability problems. Chic. J. Theoret. Comput. Sci. (1999)","DOI":"10.4086\/cjtcs.1999.008"},{"key":"17_CR16","unstructured":"Felzenszwalb, P.F., Huttenlocher, D.P.: Distance transforms of sampled functions. TR2004-1963, Faculty of Computing and Information Science, Cornell Univ"},{"key":"17_CR17","unstructured":"Fischer, M.J., Paterson, M.S.: String-matching and other products. In: Proc. SIAM-AMS Applied Math. Symp. Complexity of computation, pp. 113\u2013125 (1973)"},{"issue":"2","key":"17_CR18","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0022-0000(82)90048-4","volume":"24","author":"G.N. Frederickson","year":"1982","unstructured":"Frederickson, G.N., Johnson, D.B.: The complexity of selection and ranking in X\u2009+\u2009Y and matrices with sorted columns. J. Comput. System Sci.\u00a024(2), 197\u2013208 (1982)","journal-title":"J. Comput. System Sci."},{"issue":"4","key":"17_CR19","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1016\/0304-3975(76)90078-5","volume":"1","author":"M.L. Fredman","year":"1976","unstructured":"Fredman, M.L.: How good is the information theory bound in sorting? Theoret. Comput. Sci.\u00a01(4), 355\u2013361 (1976)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"17_CR20","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1137\/0205006","volume":"5","author":"M.L. Fredman","year":"1976","unstructured":"Fredman, M.L.: New bounds on the complexity of the shortest path problem. SIAM J. Comput.\u00a05(1), 83\u201389 (1976)","journal-title":"SIAM J. Comput."},{"key":"17_CR21","unstructured":"Gauss, C.F.: Werke, K\u00f6niglichen Gesellschaft der Wissenschaften, vol.\u00a03 (1866)"},{"issue":"3","key":"17_CR22","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF00348431","volume":"34","author":"M.T. Heideman","year":"1985","unstructured":"Heideman, M.T., Johnson, D.H., Burrus, C.S.: Gauss and the history of the fast Fourier transform. Arch. Hist. Exact Sci.\u00a034(3), 265\u2013277 (1985)","journal-title":"Arch. Hist. Exact Sci."},{"key":"17_CR23","doi-asserted-by":"crossref","unstructured":"Indyk, P.: Faster algorithms for string matching problems: Matching the convolution bound. In: Proc. 39th Symp. Found. Computer Science, pp. 166\u2013173 (1998)","DOI":"10.1109\/SFCS.1998.743440"},{"key":"17_CR24","first-page":"289","volume-title":"Nonlinear Image Processing, Ch. 10","author":"P. Maragos","year":"2000","unstructured":"Maragos, P.: Differential morphology. In: Mitra, S., Sicuranza, G. (eds.) Nonlinear Image Processing, Ch. 10, pp. 289\u2013329. Academic Press, London (2000)"},{"issue":"9","key":"17_CR25","first-page":"109","volume":"49","author":"J.-J. Moreau","year":"1970","unstructured":"Moreau, J.-J.: Inf-convolution, sous-additivit\u00e9, convexit\u00e9 des fonctions num\u00e9riques. J. Math. Pures Appl.\u00a049(9), 109\u2013154 (1970)","journal-title":"J. Math. Pures Appl."},{"key":"17_CR26","doi-asserted-by":"crossref","DOI":"10.1515\/9781400873173","volume-title":"Convex Analysis","author":"R.T. Rockafellar","year":"1970","unstructured":"Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970)"},{"issue":"5","key":"17_CR27","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/0020-0190(94)00201-9","volume":"53","author":"W.L. Steiger","year":"1995","unstructured":"Steiger, W.L., Streinu, I.: A pseudo-algorithmic separation of lines from pseudo-lines. Infor. Process. Lett.\u00a053(5), 295\u2013299 (1995)","journal-title":"Infor. Process. Lett."},{"key":"17_CR28","first-page":"58","volume":"352","author":"T. Str\u00f6mberg","year":"1996","unstructured":"Str\u00f6mberg, T.: The operation of infimal convolution. Dissertationes Math. (Rozprawy Mat.)\u00a0352, 58 (1996)","journal-title":"Dissertationes Math. (Rozprawy Mat.)"},{"key":"17_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1007\/11589440_20","volume-title":"Discrete and Computational Geometry","author":"G. Toussaint","year":"2005","unstructured":"Toussaint, G.: The geometry of musical rhythm. In: Akiyama, J., Kano, M., Tan, X. (eds.) JCDCG 2004. LNCS, vol.\u00a03742, pp. 198\u2013212. Springer, Heidelberg (2005)"},{"key":"17_CR30","unstructured":"Toussaint, G.T.: A comparison of rhythmic similarity measures. In: Proc. 5th International Conference on Music Information Retrieval, pp. 242\u2013245 (2004)"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11841036_17.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:16:49Z","timestamp":1619493409000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11841036_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540388753","9783540388760"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/11841036_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}