{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:54:14Z","timestamp":1750308854239,"version":"3.41.0"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,6,25]],"date-time":"2024-06-25T00:00:00Z","timestamp":1719273600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,6,25]],"date-time":"2024-06-25T00:00:00Z","timestamp":1719273600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["260\/18"],"award-info":[{"award-number":["260\/18"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2025,7]]},"DOI":"10.1007\/s00454-024-00673-7","type":"journal-article","created":{"date-parts":[[2024,6,25]],"date-time":"2024-06-25T14:02:08Z","timestamp":1719324128000},"page":"177-195","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Improved Algebraic Degeneracy Testing"],"prefix":"10.1007","volume":"74","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2312-0967","authenticated-orcid":false,"given":"Jean","family":"Cardinal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha","family":"Sharir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,6,25]]},"reference":[{"key":"673_CR1","first-page":"1","volume-title":"A Journey through Discrete Mathematics: A Tribute to Ji\u0159\u00ed Matou\u0161ek","author":"PK Agarwal","year":"2017","unstructured":"Agarwal, P.K.: Simplex range searching and its variants: a review. In: A Journey through Discrete Mathematics: A Tribute to Ji\u0159\u00ed Matou\u0161ek, pp. 1\u201330. Springer, Berlin (2017)"},{"key":"673_CR2","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Aronov, B., Ezra, E., Zahl, J.: Efficient algorithm for generalized polynomial partitioning and its applications. SIAM J. Comput. 50(2), 760\u2013787 (2021). (Also in Proceedings of SoCG\u201920)","DOI":"10.1137\/19M1268550"},{"key":"673_CR3","unstructured":"Agarwal, P.K., Aronov, B., Ezra, E., Katz, M.J., Sharir, M.: Intersection queries for flat semi-algebraic objects in three dimensions and related problems. In: 38th International Symposium on Computational Geometry, SoCG 2022, pp. 4:1\u20134:14, Long version on http:\/\/arxiv.org\/abs\/2203.10241 (2022)"},{"issue":"2","key":"673_CR4","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":"673_CR5","doi-asserted-by":"crossref","unstructured":"Aronov, B., Cardinal, J.: Geometric pattern matching reduces to $$k$$-SUM. Discrete Comput. Geom. 68(3), 850\u2013859 (2022). (Also in Proceedings of ISAAC\u201920)","DOI":"10.1007\/s00454-021-00324-1"},{"key":"673_CR6","doi-asserted-by":"crossref","unstructured":"Aronov, B., de Berg, M., Cardinal, J., Ezra, E., Iacono, J., Sharir, M.: Subquadratic algorithms for some 3SUM-hard geometric problems in the algebraic decision-tree model. Comput. Geom. 109, 101945 (2023). (Also in Proceedings of ISAAC\u201920)","DOI":"10.1016\/j.comgeo.2022.101945"},{"key":"673_CR7","doi-asserted-by":"crossref","unstructured":"Aronov, B., Ezra, E., Sharir, M.: Testing polynomials for vanishing on Cartesian products of planar point sets: collinearity testing and related problems. Discrete Comput. Geom. 68(4), 997\u20131048 (2022). (Also in Proceedings of SoCG\u201920)","DOI":"10.1007\/s00454-022-00437-1"},{"issue":"3","key":"673_CR8","doi-asserted-by":"publisher","first-page":"668","DOI":"10.1145\/828.322450","volume":"31","author":"FM auf der Heide","year":"1984","unstructured":"auf der Heide, F.M.: A polynomial linear search algorithm for the $$n$$-dimensional knapsack problem. J. ACM 31(3), 668\u2013676 (1984)","journal-title":"J. ACM"},{"issue":"4","key":"673_CR9","doi-asserted-by":"publisher","first-page":"584","DOI":"10.1007\/s00453-007-9036-3","volume":"50","author":"I Baran","year":"2008","unstructured":"Baran, I., Demaine, E.D., P\u01cetra\u015fcu, M.: Subquadratic algorithms for 3SUM. Algorithmica 50(4), 584\u2013596 (2008)","journal-title":"Algorithmica"},{"key":"673_CR10","doi-asserted-by":"crossref","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). (Also in Proceedings of SoCG\u201917)","DOI":"10.1007\/s00454-018-0040-y"},{"key":"673_CR11","volume-title":"Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics","author":"S Basu","year":"2006","unstructured":"Basu, S., Pollack, R., Roy, M.-F.: Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics. Springer, Berlin (2006)"},{"key":"673_CR12","doi-asserted-by":"crossref","unstructured":"Ben-Or, M.: Lower bounds for algebraic computation trees (preliminary report). In: Proceedings of the 15th Annual ACM Symposium on Theory of Computing, STOC 1983, pp. 80\u201386. ACM (1983)","DOI":"10.1145\/800061.808735"},{"key":"673_CR13","unstructured":"Cardinal, J., Iacono, J., Ooms, A.: Solving $$k$$-SUM using few linear queries. In: 24th Annual European Symposium on Algorithms, ESA 2016, pp. 25:1\u201325:17 (2016)"},{"issue":"1","key":"673_CR14","doi-asserted-by":"publisher","first-page":"7:1","DOI":"10.1145\/3363541","volume":"16","author":"TM Chan","year":"2020","unstructured":"Chan, T.M.: More logarithmic-factor speedups for 3SUM, (median, +)-convolution, and some geometric 3SUM-hard problems. ACM Trans. Algorithms 16(1), 7:1-7:23 (2020)","journal-title":"ACM Trans. Algorithms"},{"key":"673_CR15","doi-asserted-by":"crossref","unstructured":"Chan, T.M., He, Q.: Reducing 3SUM to convolution-3SUM. In: 3rd Symposium on Simplicity in Algorithms, SOSA 2020, pp. 1\u20137. SIAM (2020)","DOI":"10.1137\/1.9781611976014.1"},{"key":"673_CR16","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Zheng, D.W.: Hopcroft\u2019s problem, log-star shaving, 2D fractional cascading, and decision trees. In: Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, pp. 190\u2013210. SIAM (2022)","DOI":"10.1137\/1.9781611977073.10"},{"key":"673_CR17","volume-title":"Ideals, Varieties, and Algorithms. An Introduction to Computational Algebraic Geometry and Commutative Algebra","author":"D Cox","year":"2007","unstructured":"Cox, D., Little, J., O\u2019Shea, D.: Ideals, Varieties, and Algorithms. An Introduction to Computational Algebraic Geometry and Commutative Algebra. Springer, Heidelberg (2007)"},{"key":"673_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"M de Berg","year":"2008","unstructured":"de Berg, M., Cheong, O., van Kreveld, M.J., Overmars, M.H.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, Berlin (2008)","edition":"3"},{"key":"673_CR19","doi-asserted-by":"crossref","unstructured":"Dudek, B., Gawrychowski, P., Starikovskaya, T.: All non-trivial variants of 3-LDT are equivalent. In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pp. 974\u2013981. ACM (2020)","DOI":"10.1145\/3357713.3384275"},{"issue":"2","key":"673_CR20","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1137\/0215023","volume":"15","author":"H Edelsbrunner","year":"1986","unstructured":"Edelsbrunner, H., Guibas, L.J., Stolfi, J.: Optimal point location in a monotone subdivision. SIAM J. Comput. 15(2), 317\u2013340 (1986)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"673_CR21","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1137\/0215024","volume":"15","author":"H Edelsbrunner","year":"1986","unstructured":"Edelsbrunner, H., O\u2019Rourke, J., Seidel, R.: Constructing arrangements of lines and hyperplanes with applications. SIAM J. Comput. 15(2), 341\u2013363 (1986)","journal-title":"SIAM J. Comput."},{"key":"673_CR22","unstructured":"Erickson, J.: Bounds for linear satisfiability problems. Chic. J. Theor. Comput. Sci. (1999)"},{"key":"673_CR23","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/BF02574027","volume":"13","author":"J Erickson","year":"1995","unstructured":"Erickson, J., Seidel, R.: Better lower bounds on detecting affine and spherical degeneracies. Discrete Comput. Geom. 13, 41\u201357 (1995)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"673_CR24","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."},{"key":"673_CR25","unstructured":"Ezra, E., Sharir, M.: Intersection searching amid tetrahedra in 4-space and efficient continuous collision detection. In: 30th Annual European Symposium on Algorithms, ESA, pp. 51:1\u201351:17, 2022. To appear in Discrete Comput. Geom. (2022)"},{"issue":"6","key":"673_CR26","doi-asserted-by":"publisher","first-page":"1785","DOI":"10.4171\/jems\/705","volume":"19","author":"J Fox","year":"2017","unstructured":"Fox, J., Pach, J., Sheffer, A., Suk, A., Zahl, J.: A semi-algebraic version of Zarankiewicz\u2019s problem. J. Eur. Math. Soc. 19(6), 1785\u20131810 (2017)","journal-title":"J. Eur. Math. Soc."},{"issue":"4","key":"673_CR27","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1016\/0304-3975(76)90078-5","volume":"1","author":"ML Fredman","year":"1976","unstructured":"Fredman, M.L.: How good is the information theory bound in sorting? Theor. Comput. Sci. 1(4), 355\u2013361 (1976)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"673_CR28","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1137\/0205006","volume":"5","author":"ML Fredman","year":"1976","unstructured":"Fredman, M.L.: New bounds on the complexity of the shortest path problem. SIAM J. Comput. 5(1), 83\u201389 (1976)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"673_CR29","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"},{"key":"673_CR30","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0925-7721(95)00022-2","volume":"5","author":"A Gajentaan","year":"1995","unstructured":"Gajentaan, A., Overmars, M.H.: On a class of $${O}(n^2)$$ problems in computational geometry. Comput. Geom. 5, 165\u2013185 (1995)","journal-title":"Comput. Geom."},{"key":"673_CR31","unstructured":"Gold, O., Sharir, M.: Improved bounds for 3SUM, $$k$$-SUM, and linear degeneracy. In: 25th Annual European Symposium on Algorithms, ESA 2017, pp. 42:1\u201342:13 (2017)"},{"key":"673_CR32","doi-asserted-by":"crossref","unstructured":"Gr\u00f8nlund, A., Pettie, S.: Threesomes, degenerates, and love triangles. J. ACM 65(4), 22:1-22:25 (2018). (Also in Proceedings of FOCS\u201914)","DOI":"10.1145\/3185378"},{"key":"673_CR33","doi-asserted-by":"crossref","unstructured":"Kane, D.M., Lovett, S., Moran, S.: Near-optimal linear decision trees for $$k$$-SUM and related problems. J. ACM 66(3), 16:1-16:18 (2019). (Also in Proceedings of STOC\u201918)","DOI":"10.1145\/3285953"},{"issue":"3","key":"673_CR34","doi-asserted-by":"publisher","first-page":"594","DOI":"10.1137\/0206043","volume":"6","author":"DT Lee","year":"1977","unstructured":"Lee, D.T., Preparata, F.P.: Location of a point in a planar subdivision and its applications. SIAM J. Comput. 6(3), 594\u2013606 (1977)","journal-title":"SIAM J. Comput."},{"key":"673_CR35","unstructured":"Lincoln, A., Williams, V.V., Wang, J.R., Williams, R.R.: Deterministic time-space trade-offs for $$k$$-SUM. In: 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, pp. 58:1\u201358:14 (2016)"},{"key":"673_CR36","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF02573972","volume":"10","author":"J Matou\u0161ek","year":"1993","unstructured":"Matou\u0161ek, J.: Range searching with efficient hierarchical cuttings. Discrete Comput. Geom. 10, 157\u2013182 (1993)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"673_CR37","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1007\/s00454-015-9701-2","volume":"54","author":"J Matou\u0161ek","year":"2015","unstructured":"Matou\u0161ek, J., Pat\u00e1kov\u00e1, Z.: Multilevel polynomial partitions and simplified range searching. Discrete Comput. Geom. 54(1), 22\u201341 (2015)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"673_CR38","doi-asserted-by":"publisher","first-page":"286","DOI":"10.1006\/inco.1993.1057","volume":"106","author":"S Meiser","year":"1993","unstructured":"Meiser, S.: Point location in arrangements of hyperplanes. Inf. Comput. 106(2), 286\u2013303 (1993)","journal-title":"Inf. Comput."},{"key":"673_CR39","doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M., Williams, R.: On the possibility of faster SAT algorithms. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, pp. 1065\u20131075. SIAM (2010)","DOI":"10.1137\/1.9781611973075.86"},{"key":"673_CR40","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction. Texts and Monographs in Computer Science","author":"FP Preparata","year":"1985","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Texts and Monographs in Computer Science. Springer, Berlin (1985)"},{"issue":"4","key":"673_CR41","doi-asserted-by":"publisher","first-page":"649","DOI":"10.1145\/321724.321730","volume":"19","author":"EM Reingold","year":"1972","unstructured":"Reingold, E.M.: On the optimality of some set algorithms. J. ACM 19(4), 649\u2013659 (1972)","journal-title":"J. ACM"},{"issue":"7","key":"673_CR42","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1145\/6138.6151","volume":"29","author":"N Sarnak","year":"1986","unstructured":"Sarnak, N., Tarjan, R.E.: Planar point location using persistent search trees. Commun. ACM 29(7), 669\u2013679 (1986)","journal-title":"Commun. ACM"},{"issue":"4","key":"673_CR43","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"JT Schwartz","year":"1980","unstructured":"Schwartz, J.T.: Fast probabilistic algorithms for verification of polynomial identities. J. ACM 27(4), 701\u2013717 (1980)","journal-title":"J. ACM"},{"issue":"1","key":"673_CR44","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0196-6774(82)90002-5","volume":"3","author":"JM Steele","year":"1982","unstructured":"Steele, J.M., Yao, A.C.-C.: Lower bounds for algebraic decision trees. J. Algorithms 3(1), 1\u20138 (1982)","journal-title":"J. Algorithms"},{"key":"673_CR45","first-page":"3447","volume":"2018","author":"VV Williams","year":"2018","unstructured":"Williams, V.V.: On some fine-grained complexity questions in algorithms and complexity. Proc. Int. Congr. Math. ICM 2018, 3447\u20133487 (2018)","journal-title":"Proc. Int. Congr. Math. ICM"},{"key":"673_CR46","doi-asserted-by":"crossref","unstructured":"Zippel, R.: Probabilistic algorithms for sparse polynomials. In: Symbolic and Algebraic Computation, EUROSAM \u201979, volume\u00a072 of Lecture Notes in Computer Science, pp. 216\u2013226. Springer (1979)","DOI":"10.1007\/3-540-09519-5_73"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-024-00673-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-024-00673-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-024-00673-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:14:14Z","timestamp":1750281254000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-024-00673-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,25]]},"references-count":46,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["673"],"URL":"https:\/\/doi.org\/10.1007\/s00454-024-00673-7","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2024,6,25]]},"assertion":[{"value":"27 June 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 May 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 June 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 June 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}