{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:24:08Z","timestamp":1750281848213,"version":"3.37.3"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,9,27]],"date-time":"2021-09-27T00:00:00Z","timestamp":1632700800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,9,27]],"date-time":"2021-09-27T00:00:00Z","timestamp":1632700800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2022,10]]},"DOI":"10.1007\/s00454-021-00324-1","type":"journal-article","created":{"date-parts":[[2021,9,27]],"date-time":"2021-09-27T14:02:44Z","timestamp":1632751364000},"page":"850-859","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Geometric Pattern Matching Reduces to k -SUM"],"prefix":"10.1007","volume":"68","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3110-4702","authenticated-orcid":false,"given":"Boris","family":"Aronov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2312-0967","authenticated-orcid":false,"given":"Jean","family":"Cardinal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,9,27]]},"reference":[{"issue":"3","key":"324_CR1","doi-asserted-by":"publisher","first-page":"1098","DOI":"10.1137\/15M1050987","volume":"47","author":"A Abboud","year":"2018","unstructured":"Abboud, A., Vassilevska Williams, V., Yu, H.: Matching triangles and basing hardness on an extremely popular conjecture. SIAM J. Comput. 47(3), 1098\u20131122 (2018)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"324_CR2","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1007\/s00493-004-0033-8","volume":"24","author":"BM \u00c1brego","year":"2004","unstructured":"\u00c1brego, B.M., Elekes, G., Fern\u00e1ndez-Merchant, S.: Structural results for planar sets with many similar subsets. Combinatorica 24(4), 541\u2013554 (2004)","journal-title":"Combinatorica"},{"issue":"1","key":"324_CR3","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/PL00009486","volume":"23","author":"BM \u00c1brego","year":"2000","unstructured":"\u00c1brego, B.M., Fern\u00e1ndez-Merchant, S.: On the maximum number of equilateral triangles. I. Discrete Comput. Geom. 23(1), 129\u2013135 (2000)","journal-title":"Discrete Comput. Geom."},{"key":"324_CR4","doi-asserted-by":"crossref","unstructured":"\u00c1brego, B.M., Fern\u00e1ndez-Merchant, S., Katz, D.J., Kolesnikov, L.: On the number of similar instances of a pattern in a finite set. Electron. J. Comb. 23(4), #\u00a04.39 (2016)","DOI":"10.37236\/4972"},{"issue":"2","key":"324_CR5","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/s00454-002-0727-x","volume":"28","author":"PK Agarwal","year":"2002","unstructured":"Agarwal, P.K., Sharir, M.: The number of congruent simplices in a point set. Discrete Comput. Geom. 28(2), 123\u2013150 (2002)","journal-title":"Discrete Comput. Geom."},{"issue":"16","key":"324_CR6","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1016\/j.ipl.2009.04.021","volume":"109","author":"D Aiger","year":"2009","unstructured":"Aiger, D., Kedem, K.: Geometric pattern matching for point sets in the plane under similarity transformations. Inform. Process. Lett. 109(16), 935\u2013940 (2009)","journal-title":"Inform. Process. Lett."},{"issue":"2","key":"324_CR7","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1145\/1059513.1059515","volume":"52","author":"N Ailon","year":"2005","unstructured":"Ailon, N., Chazelle, B.: Lower bounds for linear degeneracy testing. J. ACM 52(2), 157\u2013171 (2005)","journal-title":"J. ACM"},{"key":"324_CR8","unstructured":"Aronov, B., Ezra, E., Sharir, M.: Testing polynomials for vanishing on Cartesian products of planar point sets. In: 36th International Symposium on Computational Geometry (Z\u00fcrich 2020). Leibniz Int. Proc. Inform., vol.\u00a0164, #\u00a08. Leibniz-Zent. Inform., Wadern (2020)"},{"key":"324_CR9","unstructured":"Aronov, B., Ezra, E., Sharir, M.: Testing polynomials for vanishing on Cartesian products of planar point setss: collinearity testing and related problems (2020). arXiv:2003.09533"},{"issue":"4","key":"324_CR10","doi-asserted-by":"publisher","first-page":"698","DOI":"10.1007\/s00454-018-0040-y","volume":"61","author":"L Barba","year":"2019","unstructured":"Barba, L., Cardinal, J., Iacono, J., Langerman, S., Ooms, A., Solomon, N.: Subquadratic algorithms for algebraic 3SUM. Discrete Comput. Geom. 61(4), 698\u2013734 (2019)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"324_CR11","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1007\/s00454-002-2884-3","volume":"28","author":"P Bra\u00df","year":"2002","unstructured":"Bra\u00df, P.: Combinatorial geometry problems in pattern recognition. Discrete Comput. Geom. 28(4), 495\u2013510 (2002)","journal-title":"Discrete Comput. Geom."},{"key":"324_CR12","doi-asserted-by":"crossref","unstructured":"Brass, P., Pach, J.: Problems and results on geometric patterns. In: Graph Theory and Combinatorial Optimization. GERAD 25th Anniv. Ser., vol. 8, pp. 17\u201336. Springer, New York (2005)","DOI":"10.1007\/0-387-25592-3_2"},{"key":"324_CR13","unstructured":"Cardinal, J., Iacono, J., Ooms, A.: Solving $$k$$-SUM using few linear queries. In: 24th Annual European Symposium on Algorithms (Aarhus 2016). Leibniz Int. Proc. Inform., vol.\u00a057, #\u00a025. Leibniz-Zent. Inform., Wadern (2016)"},{"key":"324_CR14","doi-asserted-by":"crossref","unstructured":"Chan, T.M.: More logarithmic-factor speedups for 3SUM, (median,+)-convolution, and some geometric 3SUM-hard problems. In: 29th Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans 2018), pp. 881\u2013897. SIAM, Philadelphia (2018)","DOI":"10.1137\/1.9781611975031.57"},{"issue":"1\u20132","key":"324_CR15","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/0925-7721(95)00047-X","volume":"7","author":"LP Chew","year":"1997","unstructured":"Chew, L.P., Goodrich, M.T., Huttenlocher, D.P., Kedem, K., Kleinberg, J.M., Kravets, D.: Geometric pattern matching under Euclidean motion. Comput. Geom. 7(1\u20132), 113\u2013124 (1997)","journal-title":"Comput. Geom."},{"key":"324_CR16","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8643-8","volume-title":"Non-Uniform Random Variate Generation","author":"L Devroye","year":"1986","unstructured":"Devroye, L.: Non-Uniform Random Variate Generation. Springer, New York (1986)"},{"key":"324_CR17","doi-asserted-by":"crossref","unstructured":"Dudek, B., Gawrychowski, P., Starikovskaya, T.: All non-trivial variants of 3-LDT are equivalent. In: 52nd Annual ACM Symposium on Theory of Computing (Chicago 2020), pp. 974\u2013981. ACM, New York (2020)","DOI":"10.1145\/3357713.3384275"},{"key":"324_CR18","unstructured":"Elekes, G.; Erd\u0151s, P.: Similar configurations and pseudo grids. In: Intuitive Geometry (Szeged 1991). Colloq. Math. Soc. J\u00e1nos Bolyai, vol. 63, pp. 85\u2013104. North-Holland, Amsterdam (1994)"},{"issue":"4","key":"324_CR19","doi-asserted-by":"publisher","first-page":"735","DOI":"10.1007\/s00454-018-0043-8","volume":"61","author":"E Ezra","year":"2019","unstructured":"Ezra, E., Sharir, M.: A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model. Discrete Comput. Geom. 61(4), 735\u2013755 (2019)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"324_CR20","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1007\/s00453-015-0079-6","volume":"77","author":"A Freund","year":"2017","unstructured":"Freund, A.: Improved subquadratic 3SUM. Algorithmica 77(2), 440\u2013458 (2017)","journal-title":"Algorithmica"},{"issue":"1","key":"324_CR21","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/s00453-003-1043-4","volume":"38","author":"M Gavrilov","year":"2004","unstructured":"Gavrilov, M., Indyk, P., Motwani, R., Venkatasubramanian, S.: Combinatorial and experimental methods for approximate point pattern matching. Algorithmica 38(1), 59\u201390 (2004)","journal-title":"Algorithmica"},{"key":"324_CR22","unstructured":"Gold, O., Sharir, M.: Improved bounds for 3SUM, $$k$$-SUM, and linear degeneracy. In: 25th European Symposium on Algorithms (Vienna 2017). Leibniz Int. Proc. Inform., vol.\u00a087, #\u00a042. Leibniz-Zent. Inform., Wadern (2017)"},{"key":"324_CR23","unstructured":"Goodman, J.E., O\u2019Rourke, J., T\u00f3th, C.D. (eds.): Handbook of Discrete and Computational Geometry. CRC Press, Boca Raton (2017)"},{"issue":"4","key":"324_CR24","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1109\/34.761267","volume":"21","author":"MT Goodrich","year":"1999","unstructured":"Goodrich, M.T., Mitchell, J.S.B., Orletsky, M.W.: Approximate geometric pattern matching under rigid motions. IEEE Trans. Pattern Anal. Mach. Intell. 21(4), 371\u2013379 (1999)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"4","key":"324_CR25","doi-asserted-by":"publisher","first-page":"# 22","DOI":"10.1145\/3185378","volume":"65","author":"A Gr\u00f8nlund","year":"2018","unstructured":"Gr\u00f8nlund, A., Pettie, S.: Threesomes, degenerates, and love triangles. J. ACM 65(4), # 22 (2018)","journal-title":"J. ACM"},{"issue":"1","key":"324_CR26","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1007\/s00453-014-9946-9","volume":"74","author":"Z Jafargholi","year":"2016","unstructured":"Jafargholi, Z., Viola, E.: 3SUM, 3XOR, triangles. Algorithmica 74(1), 326\u2013343 (2016)","journal-title":"Algorithmica"},{"issue":"3","key":"324_CR27","doi-asserted-by":"publisher","first-page":"# 16","DOI":"10.1145\/3285953","volume":"66","author":"DM Kane","year":"2019","unstructured":"Kane, D.M., Lovett, S., Moran, S.: Near-optimal linear decision trees for $$k$$-SUM and related problems. J. ACM 66(3), # 16 (2019)","journal-title":"J. ACM"},{"key":"324_CR28","doi-asserted-by":"crossref","unstructured":"Laczkovich, M., Ruzsa, I.Z.: The number of homothetic subsets. In: The Mathematics of Paul Erd\u0151s, vol.\u00a02. Algorithms Combin., vol. 14, pp. 294\u2013302. Springer, Berlin (1997)","DOI":"10.1007\/978-3-642-60406-5_26"},{"key":"324_CR29","doi-asserted-by":"crossref","unstructured":"Vassilevska Williams, V.: On some fine-grained questions in algorithms and complexity. In: International Congress of Mathematicians (Rio de Janeiro 2018), vol.\u00a04. Invited Lectures, pp. 3447\u20133487. World Sci. Publ., Hackensack (2018)","DOI":"10.1142\/9789813272880_0188"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-021-00324-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-021-00324-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-021-00324-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,12]],"date-time":"2022-09-12T19:03:08Z","timestamp":1663009388000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-021-00324-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,27]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["324"],"URL":"https:\/\/doi.org\/10.1007\/s00454-021-00324-1","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2021,9,27]]},"assertion":[{"value":"28 October 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 July 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 July 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 September 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}