{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:34Z","timestamp":1740109594317,"version":"3.37.3"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,6,3]],"date-time":"2024-06-03T00:00:00Z","timestamp":1717372800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,6,3]],"date-time":"2024-06-03T00:00:00Z","timestamp":1717372800000},"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":["824\/17","800\/22","260\/18","595\/23"],"award-info":[{"award-number":["824\/17","800\/22","260\/18","595\/23"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2022131"],"award-info":[{"award-number":["2022131"]}],"id":[{"id":"10.13039\/100006221","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,3]]},"DOI":"10.1007\/s00454-024-00656-8","type":"journal-article","created":{"date-parts":[[2024,6,3]],"date-time":"2024-06-03T14:04:11Z","timestamp":1717423451000},"page":"327-369","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Intersection Searching amid Tetrahedra in Four Dimensions"],"prefix":"10.1007","volume":"73","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8133-1335","authenticated-orcid":false,"given":"Esther","family":"Ezra","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2541-3763","authenticated-orcid":false,"given":"Micha","family":"Sharir","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,6,3]]},"reference":[{"key":"656_CR1","doi-asserted-by":"publisher","unstructured":"Afshani, P., Cheng, P.: Lower bounds for intersection reporting among flat objects. In: 39th International Symposium on Computational Geometry, pp. 3:1\u20133:16 (2023). https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2023.3","DOI":"10.4230\/LIPIcs.SoCG.2023.3"},{"issue":"2","key":"656_CR2","doi-asserted-by":"publisher","first-page":"16:1","DOI":"10.1145\/3578574","volume":"70","author":"P Afshani","year":"2023","unstructured":"Afshani, P., Cheng, P.: Lower bounds for semialgebraic range searching and stabbing problems. J. ACM 70(2), 16:1-16:26 (2023). https:\/\/doi.org\/10.1145\/3578574","journal-title":"J. ACM"},{"key":"656_CR3","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K.: Simplex range searching and its variants: a review. In: Journey through Discrete Mathematics: A Tribute to Ji\u0159\u00ed Matou\u0161ek, pp. 1\u201330. Springer, Berlin (2017)","DOI":"10.1007\/978-3-319-44479-6_1"},{"key":"656_CR4","unstructured":"Agarwal, P.K., Aronov, B., Ezra, E., Katz, M., Sharir, M.: Intersection queries for flat semi-algebraic objects in three dimensions and related problems. In: Proceedings of 38th Symposium on Computational Geometry, pp. 4:1\u20134:14 (2022). Also in arXiv:2203.10241"},{"key":"656_CR5","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Aronov, B., Ezra, E., Zahl, J.: An efficient algorithm for generalized polynomial partitioning and its applications. SIAM J. Comput., 50, 760\u2013787 (2021). Also in Proceedings of Symposium on Computational Geometry (SoCG), 5:1\u20135:14 (2019). Also in arXiv:1812.10269","DOI":"10.1137\/19M1268550"},{"key":"656_CR6","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Erickson, J.: Geometric range searching and its relatives. In: Advances in Discrete and Computational Geometry, volume 223 of Contemporary Mathematics, pp. 1\u201356. AMS Press, Providence, RI (1999)","DOI":"10.1090\/conm\/223\/03131"},{"key":"656_CR7","doi-asserted-by":"publisher","first-page":"794","DOI":"10.1137\/0222051","volume":"22","author":"PK Agarwal","year":"1993","unstructured":"Agarwal, P.K., Matou\u0161ek, J.: Ray shooting and parameric search. SIAM J. Comput. 22, 794\u2013806 (1993)","journal-title":"SIAM J. Comput."},{"key":"656_CR8","doi-asserted-by":"publisher","first-page":"2039","DOI":"10.1137\/120890855","volume":"42","author":"PK Agarwal","year":"2013","unstructured":"Agarwal, P.K., Matou\u0161ek, J., Sharir, M.: On range searching with semialgebraic sets II. SIAM J. Comput. 42, 2039\u20132062 (2013). arXiv:1208.3384","journal-title":"SIAM J. Comput."},{"key":"656_CR9","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, 997\u20131048 (2022). Also in Proceeding of 36th Symposium on Computational Geometry, 8:1\u20138:14 (2020). Also in arXiv:2003.09533","DOI":"10.1007\/s00454-022-00437-1"},{"issue":"6","key":"656_CR10","doi-asserted-by":"publisher","first-page":"1109","DOI":"10.1137\/19M1257548","volume":"49","author":"B Aronov","year":"2020","unstructured":"Aronov, B., Ezra, E., Zahl, J.: Constructive polynomial partitioning for algebraic curves in $$\\mathbb{R} ^{3}$$ with applications. SIAM J. Comput. 49(6), 1109\u20131127 (2020). https:\/\/doi.org\/10.1137\/19M1257548","journal-title":"SIAM J. Comput."},{"key":"656_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-33099-2","volume-title":"Algorithms in Real Algebraic Geometry","author":"S Basu","year":"2006","unstructured":"Basu, S., Pollack, R., Roy, M.-F.: Algorithms in Real Algebraic Geometry, 2nd edn. Springer, Berlin (2006)","edition":"2"},{"key":"656_CR12","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1109\/TPAMI.1986.4767773","volume":"8","author":"J Canny","year":"1986","unstructured":"Canny, J.: Collision detection for moving polyhedra. IEEE Trans. Pattern Anal. Mach. Intell. (PAMI) 8, 200\u2013209 (1986)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell. (PAMI)"},{"issue":"3","key":"656_CR13","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/BF02122778","volume":"10","author":"B Chazelle","year":"1990","unstructured":"Chazelle, B., Friedman, J.: A deterministic view of random sampling and its use in geometry. Combinatorica 10(3), 229\u2013249 (1990)","journal-title":"Combinatorica"},{"key":"656_CR14","doi-asserted-by":"crossref","unstructured":"Collins, G.E.: Quantifier elimination for the elementary theory of real closed fields by cylindrical algebraic decomposition. In: Proceedings of 2nd GI Conference Automata Theory and Formal Languages, volume\u00a033. Springer LNCS (1975)","DOI":"10.1007\/3-540-07407-4_17"},{"key":"656_CR15","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, Berlin-Heidelberg (2007)"},{"key":"656_CR16","doi-asserted-by":"crossref","unstructured":"de\u00a0Berg, M., Cheong, O., van Kreveld, M.J., Overmars, M.H.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer (2008). https:\/\/www.worldcat.org\/oclc\/227584184","DOI":"10.1007\/978-3-540-77974-2"},{"key":"656_CR17","unstructured":"Ezra, E., Sharir, M.: Intersection searching amid tetrahedra in 4-space and efficient continuous collision detection. In: Proceedings of 30th European Symposium Algorithms, pp. 51:1\u201351:17 (2022). Also in arXiv:2208.06703"},{"key":"656_CR18","doi-asserted-by":"crossref","unstructured":"Ezra, E., Sharir, M.: On ray shooting for triangles in 3-space and related problems. SIAM J. Comput., 51, 1065\u20131095 (2022). Also in Proceedings of 37th Symposium on Computational Geometry, 34:1\u201334:15 (2021), and in arXiv:2102.07310","DOI":"10.1137\/21M1408245"},{"key":"656_CR19","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1006\/jcom.1995.1007","volume":"11","author":"A Galligo","year":"1995","unstructured":"Galligo, A., Vorobjov, N.: Complexity of finding irreducible components of a semialgebraic set. J. Complex. 11, 174\u2013193 (1995)","journal-title":"J. Complex."},{"key":"656_CR20","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1017\/S0305004115000468","volume":"159","author":"L Guth","year":"2015","unstructured":"Guth, L.: Polynomial partitioning for a set of varieties. Math. Proc. Camb. Philos. Soc. 159, 459\u2013469 (2015). arXiv:1410.8871","journal-title":"Math. Proc. Camb. Philos. Soc."},{"key":"656_CR21","doi-asserted-by":"publisher","first-page":"155","DOI":"10.4007\/annals.2015.181.1.2","volume":"181","author":"L Guth","year":"2015","unstructured":"Guth, L., Katz, N.H.: On the Erd\u00f6s distinct distances problem in the plane. Ann. Math. 181, 155\u2013190 (2015). arXiv:1011.4105","journal-title":"Ann. Math."},{"key":"656_CR22","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D Haussler","year":"1987","unstructured":"Haussler, D., Welzl, E.: Epsilon-nets and simplex range queries. Discrete Comput. Geom. 2, 127\u2013151 (1987)","journal-title":"Discrete Comput. Geom."},{"key":"656_CR23","doi-asserted-by":"crossref","unstructured":"Kaltofen, E.: Polynomial factorization 1987-1991. In: Proceedings of 1st Latin American Symposium Theoretical Informatics, pp. 294\u2013313. Lecture Notes in Computer Science, vol. 583 (1992)","DOI":"10.1007\/BFb0023837"},{"key":"656_CR24","unstructured":"Lin, M.C., Manocha, D., Kim, Y.J.: Collision and proximity queries. In: Handbook on Discrete and Computational Geometry, chapter\u00a039, 3rd edn, pp. 1029\u20131056. CRC Press, Boca Raton (2017)"},{"key":"656_CR25","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."},{"key":"656_CR26","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, 22\u201341 (2015)","journal-title":"Discrete Comput. Geom."},{"key":"656_CR27","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1007\/BF01187036","volume":"9","author":"M Pellegrini","year":"1993","unstructured":"Pellegrini, M.: Ray shooting on triangles in 3-space. Algorithmica 9, 471\u2013494 (1993)","journal-title":"Algorithmica"},{"key":"656_CR28","volume-title":"A Treatise on the Analytic Geometry of Three Dimensions","author":"G Salmon","year":"1915","unstructured":"Salmon, G.: A Treatise on the Analytic Geometry of Three Dimensions, vol. 2, 5th edn. Hodges, Figgis and co. Ltd., Dublin (1915)","edition":"5"},{"key":"656_CR29","doi-asserted-by":"crossref","unstructured":"Sch\u00f6mer, E., Thiel, Ch.: Efficient collision detection for moving polyhedra. In: Proceedings of 11th Symposium on Computational Geometry, pp. 51\u201360 (1995)","DOI":"10.1145\/220279.220285"},{"key":"656_CR30","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1016\/0196-8858(83)90014-3","volume":"4","author":"JT Schwartz","year":"1983","unstructured":"Schwartz, J.T., Sharir, M.: On the piano movers\u2019 problem: II. General techniques for computing topological properties of real algebraic manifolds. Adv. Appl. Math. 4, 298\u2013351 (1983)","journal-title":"Adv. Appl. Math."},{"key":"656_CR31","volume-title":"Davenport-Schinzel Sequences and Their Geometric Applications","author":"M Sharir","year":"1995","unstructured":"Sharir, M., Agarwal, P.K.: Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, Cambridge (1995)"},{"key":"656_CR32","doi-asserted-by":"publisher","DOI":"10.1017\/9781108959988","volume-title":"Polynomial Methods and Incidence Theory. Cambridge Studies in Advanced Mathematics","author":"Adam Sheffer","year":"2022","unstructured":"Sheffer, Adam: Polynomial Methods and Incidence Theory. Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge (2022)"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-024-00656-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-024-00656-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-024-00656-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,18]],"date-time":"2025-02-18T05:15:55Z","timestamp":1739855755000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-024-00656-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,3]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["656"],"URL":"https:\/\/doi.org\/10.1007\/s00454-024-00656-8","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2024,6,3]]},"assertion":[{"value":"21 January 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 April 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 April 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 June 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}