{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T14:33:41Z","timestamp":1740148421363,"version":"3.37.3"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,2,23]],"date-time":"2024-02-23T00:00:00Z","timestamp":1708646400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,2,23]],"date-time":"2024-02-23T00:00:00Z","timestamp":1708646400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"ATHENA - Research and Innovation Center in Information, Communication and Knowledge Technology"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math.Comput.Sci."],"published-print":{"date-parts":[[2024,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The Canny\u2013Emiris formula (Canny and Emiris in International symposium on applied algebra, algebraic algorithms, and error-correcting codes, 1993) gives the sparse resultant as the ratio of the determinant of a Sylvester-type matrix over a minor of it, both obtained via a mixed subdivision algorithm. In Checa and Emiris (Proceedings of the 2022 international symposium on symbolic and algebraic computation, 2022), the same authors gave an explicit class of mixed subdivisions for the greedy approach so that the formula holds, and the dimension of the constructed matrices is smaller than that of the subdivision algorithm, following the approach of Canny and Pedersen (An algorithm for the Newton resultant, 1993). Our method improves upon the dimensions of the matrices when the Newton polytopes are zonotopes and the systems are multihomogeneous. In this text, we provide more such cases, and we conjecture which might be the liftings providing minimal size of the resultant matrices. We also describe two applications of this formula, namely in computer vision and in the implicitization of surfaces, while offering the corresponding <jats:italic>JULIA<\/jats:italic> code. We finally introduce a novel tropical approach that leads to an alternative proof of a result in Checa and Emiris (Proceedings of the 2022 international symposium on symbolic and algebraic computation, 2022).<\/jats:p>","DOI":"10.1007\/s11786-024-00577-y","type":"journal-article","created":{"date-parts":[[2024,2,23]],"date-time":"2024-02-23T02:02:35Z","timestamp":1708653755000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Mixed Subdivisions Suitable for the Greedy Canny\u2013Emiris Formula"],"prefix":"10.1007","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3477-8876","authenticated-orcid":false,"given":"Carles","family":"Checa","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2339-5303","authenticated-orcid":false,"given":"Ioannis Z.","family":"Emiris","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,2,23]]},"reference":[{"issue":"1","key":"577_CR1","first-page":"243","volume":"18","author":"A Awane","year":"2005","unstructured":"Awane, A., Chkiriba, A., Goze, M.: Formes d\u2019inertie et complexe de Koszul associ\u00e9s \u00e0 des polyn\u00f4mes plurihomog\u00e8nes. Revista Matem \u00e1 tica Complutense 18(1), 243\u2013260 (2005)","journal-title":"Revista Matem \u00e1 tica Complutense"},{"issue":"1","key":"577_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01389151","volume":"87","author":"D Bayer","year":"1987","unstructured":"Bayer, D., Stillman, M.: A criterion for detecting m-regularity. Invent. Math. 87(1), 1\u201311 (1987). https:\/\/doi.org\/10.1007\/BF01389151","journal-title":"Invent. Math."},{"key":"577_CR3","unstructured":"Bender, M.R.: Algorithms for sparse polynomial systems : Grobner basis and resultants. 2019. Universite Pierre et Marie Curie\u2014Paris VI, October 2014: phdthesis"},{"issue":"4","key":"577_CR4","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1137\/20M1332190","volume":"5","author":"MR Bender","year":"2021","unstructured":"Bender, M.R., Faug\u00e8re, J.-C., Mantzaflaris, A., Tsigaridas, E.: Koszul-type determinantal formulas for families of mixed multilinear systems. SIAM J. Appl. Algebra Geometry 5(4), 589\u2013619 (2021). https:\/\/doi.org\/10.1137\/20M1332190","journal-title":"SIAM J. Appl. Algebra Geometry"},{"key":"577_CR5","doi-asserted-by":"publisher","unstructured":"Bender, M.R., Faug\u00e8re, J.-C., Tsigaridas, E.: Towards mixed Gr\u00f6bner basis algorithms: the multihomogeneous and sparse case. In: Proceedings of the 43rd International Symposium on Symbolic and Algebraic Computation (2018). https:\/\/doi.org\/10.1145\/3208976.3209018. https:\/\/hal.inria.fr\/hal-01787423","DOI":"10.1145\/3208976.3209018"},{"key":"577_CR6","doi-asserted-by":"crossref","unstructured":"Bhayani, S., Kukelova, Z., Heikkil\u00e4, J.: A Sparse resultant based method for efficient minimal solvers. In: 2020 IEEE\/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 1767\u20131776 (2019)","DOI":"10.1109\/CVPR42600.2020.00184"},{"key":"577_CR7","doi-asserted-by":"publisher","unstructured":"Bus\u00e9, L.: Implicit matrix representations of rational B\u00e9zier curves and surfaces. In: Computer-Aided Design. 2013 SIAM Conference on Geometric and Physical Modeling, vol. 46, pp. 14\u201324 (2014). https:\/\/doi.org\/10.1016\/j.cad.2013.08.014. https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0010448513001541","DOI":"10.1016\/j.cad.2013.08.014"},{"key":"577_CR8","doi-asserted-by":"publisher","unstructured":"Bus\u00e9, L., Laroche, C., Yildirim, F.: Implicitizing rational curves by the method of moving quadrics. In: Computer-Aided Design. Proceedings of the Symposium on Physical and Solid Modeling (SPM) 2019, vol. 114, pp. 101\u2013111 (2019). https:\/\/doi.org\/10.1016\/j.cad.2019.05.019. https:\/\/inria.hal.science\/hal-02112538","DOI":"10.1016\/j.cad.2019.05.019"},{"key":"577_CR9","doi-asserted-by":"crossref","unstructured":"Canny, J.F., Emiris, I.Z.: An efficient algorithm for the sparse mixed resultant. In: International Symposium on Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes, vol. 673, pp. 89\u2013104 (1993)","DOI":"10.1007\/3-540-56686-4_36"},{"key":"577_CR10","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1006\/jsco.1995.1041","volume":"20","author":"JF Canny","year":"1995","unstructured":"Canny, J.F., Emiris, I.Z.: Efficient incremental algorithms for the sparse resultant and the mixed volume. J. Symb. Comput. 20, 117\u2013149 (1995). https:\/\/doi.org\/10.1006\/jsco.1995.1041","journal-title":"J. Symb. Comput."},{"key":"577_CR11","unstructured":"Canny, J.F., Pedersen, P.: An Algorithm for the Newton Resultant. Tech. rep. NY, USA, Cornell University (1993)"},{"key":"577_CR12","doi-asserted-by":"publisher","unstructured":"Checa, C., Emiris, I.: A greedy approach to the Canny\u2013Emiris formula. In: Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation. ISSAC \u201922. pp. 283\u2013291. ACM, Villeneuve-d\u2019Ascq (2022). ISBN:9781450386883. https:\/\/doi.org\/10.1145\/3476446.3536180","DOI":"10.1145\/3476446.3536180"},{"key":"577_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/b138611","volume-title":"Using Algebraic Geometry","author":"D Cox","year":"2015","unstructured":"Cox, D., Little, J., O\u2019Shea, D.: Using Algebraic Geometry, vol. 185. Springer, New York (2015). https:\/\/doi.org\/10.1007\/b138611"},{"key":"577_CR14","doi-asserted-by":"publisher","unstructured":"Cox, D., Little, J.B., Schenck, H.: Toric Varieties. (2012). https:\/\/doi.org\/10.1365\/s13291-012-0048-9","DOI":"10.1365\/s13291-012-0048-9"},{"key":"577_CR15","doi-asserted-by":"publisher","DOI":"10.2307\/3073009","author":"C D\u2019Andrea","year":"2001","unstructured":"D\u2019Andrea, C.: Macaulay style formulas for sparse resultants. Trans. AMS (2001). https:\/\/doi.org\/10.2307\/3073009","journal-title":"Trans. AMS"},{"key":"577_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10208-021-09547-3","volume":"23","author":"C D\u2019Andrea","year":"2022","unstructured":"D\u2019Andrea, C., Jeronimo, G., Sombra, M.: The Canny\u2013Emiris conjecture for the sparse resultant. Found. Comput. Math. 23, 1\u201361 (2022). https:\/\/doi.org\/10.1007\/s10208-021-09547-3","journal-title":"Found. Comput. Math."},{"issue":"4","key":"577_CR17","doi-asserted-by":"publisher","first-page":"932","DOI":"10.1112\/plms\/pdu069","volume":"110","author":"C D\u2019Andrea","year":"2015","unstructured":"D\u2019Andrea, C., Sombra, M.: A Poisson formula for the sparse resultant. Proc. Lond. Math. Soc. 110(4), 932\u2013964 (2015). https:\/\/doi.org\/10.1112\/plms\/pdu069","journal-title":"Proc. Lond. Math. Soc."},{"key":"577_CR18","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/S0747-7171(03)00086-5","volume":"36","author":"A Dickenstein","year":"2003","unstructured":"Dickenstein, A., Emiris, I.Z.: Multihomogeneous resultant formulae by means of complexes. J. Symb. Comput. 36, 317\u2013342 (2003). https:\/\/doi.org\/10.1016\/S0747-7171(03)00086-5","journal-title":"J. Symb. Comput."},{"key":"577_CR19","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2011.12.010","author":"I Emiris","year":"2012","unstructured":"Emiris, I., Mantzaflaris, A.: Multihomogeneous resultant formulae for systems with scaled support. J. Symb. Comput. (2012). https:\/\/doi.org\/10.1016\/j.jsc.2011.12.010","journal-title":"J. Symb. Comput."},{"issue":"1","key":"577_CR20","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1006\/jsco.1998.0266","volume":"28","author":"IZ Emiris","year":"1999","unstructured":"Emiris, I.Z., Mourrain, B.: Matrices in elimination theory. J. Symb. Comput. 28(1), 3\u201344 (1999). https:\/\/doi.org\/10.1006\/jsco.1998.0266","journal-title":"J. Symb. Comput."},{"key":"577_CR21","doi-asserted-by":"publisher","unstructured":"Emiris, I.Z., Rege, A.: Monomial bases and polynomial system solving. In: MacCallum, M.A.H. (ed.) Proceedings of the International Symposium on Symbolic and Algebraic Computation, pp. 114\u2013122 (1994). https:\/\/doi.org\/10.1145\/190347.190374","DOI":"10.1145\/190347.190374"},{"key":"577_CR22","unstructured":"Emiris, I.Z.: Sparse Elimination and Applications in Kinematics. PhD thesis. Berkeley, USA: University of California at Berkeley (1994)"},{"key":"577_CR23","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/j.tcs.2012.10.018","volume":"479","author":"IZ Emiris","year":"2013","unstructured":"Emiris, I.Z., Kalinka, T., Konaxis, C., Ba, T.L.: Implicitization of curves and (hyper)surfaces using predicted support. Theor. Comput. Sci. 479, 81\u201398 (2013). https:\/\/doi.org\/10.1016\/j.tcs.2012.10.018","journal-title":"Theor. Comput. Sci."},{"key":"577_CR24","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-8176-4771-1","volume-title":"Discriminants, Resultants, and Multidimensional Determinants","author":"M Gelfand","year":"1994","unstructured":"Gelfand, M., Kapranov, M., Zelevinsky, A.: Discriminants, Resultants, and Multidimensional Determinants. Birkhauser, Basel (1994)"},{"key":"577_CR25","doi-asserted-by":"publisher","DOI":"10.1364\/JOSAA.8.001630","author":"B Horn","year":"1991","unstructured":"Horn, B.: Relative orientation revisited. J. Opt. Soc. Am A (1991). https:\/\/doi.org\/10.1364\/JOSAA.8.001630","journal-title":"J. Opt. Soc. Am A"},{"key":"577_CR26","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/j.jalgebra.2013.03.031","volume":"387","author":"A Jensen","year":"2013","unstructured":"Jensen, A., Yu, J.: Computing tropical resultants. J. Algebra 387, 287\u2013319 (2013). https:\/\/doi.org\/10.1016\/j.jalgebra.2013.03.031","journal-title":"J. Algebra"},{"key":"577_CR27","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1038\/293133a0","volume":"293","author":"HC Longuet-Higgins","year":"1981","unstructured":"Longuet-Higgins, H.C.: A computer algorithm for reconstructing a scene from two projections. Nature 293, 133\u2013135 (1981)","journal-title":"Nature"},{"key":"577_CR28","first-page":"3","volume":"35","author":"FS Macaulay","year":"1903","unstructured":"Macaulay, F.S.: Some formulae in elimination. Proc. Lond. Math. Soc. 35, 3\u201327 (1903)","journal-title":"Proc. Lond. Math. Soc."},{"key":"577_CR29","series-title":"Graduate Studies in Mathematics","doi-asserted-by":"crossref","first-page":"vii+359","DOI":"10.1090\/gsm\/161","volume-title":"Introduction to Tropical Geometry","author":"D Maclagan","year":"2015","unstructured":"Maclagan, D., Sturmfels, B.: Introduction to Tropical Geometry. Graduate Studies in Mathematics, vol. 161, p. vii+359. AMS, Providence (2015)"},{"issue":"3","key":"577_CR30","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/PL00009506","volume":"23","author":"T Michiels","year":"2000","unstructured":"Michiels, T., Cools, R.: Decomposing the secondary cayley polytope. Discrete Comput. Geometry 23(3), 367\u2013380 (2000). https:\/\/doi.org\/10.1007\/PL00009506","journal-title":"Discrete Comput. Geometry"},{"key":"577_CR31","doi-asserted-by":"publisher","first-page":"476","DOI":"10.1016\/j.jcta.2016.06.013","volume":"144","author":"RP Stanley","year":"2016","unstructured":"Stanley, R.P.: Smith normal form in combinatorics. J. Comb. Theory Ser. A 144, 476\u2013495 (2016). https:\/\/doi.org\/10.1016\/j.jcta.2016.06.013","journal-title":"J. Comb. Theory Ser. A"},{"key":"577_CR32","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1023\/A:1022497624378","volume":"3","author":"B Sturmfels","year":"1994","unstructured":"Sturmfels, B.: On the Newton polytope of the resultant. J. Algebraic Comb. 3, 207\u2013236 (1994)","journal-title":"J. Algebraic Comb."},{"key":"577_CR33","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1006\/jabr.1994.1007","volume":"163","author":"B Sturmfels","year":"1994","unstructured":"Sturmfels, B., Zelevinsky, A.: Multigraded resultants of Sylvester type. J. Algebra 163, 115\u2013127 (1994)","journal-title":"J. Algebra"},{"key":"577_CR34","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8431-1","volume-title":"Lectures on Polytopes","author":"GM Ziegler","year":"1995","unstructured":"Ziegler, G.M.: Lectures on Polytopes. Graduate Texts in Mathematics, vol. 152, 1st edn. Springer, New York (1995)","edition":"1"}],"container-title":["Mathematics in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11786-024-00577-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11786-024-00577-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11786-024-00577-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,22]],"date-time":"2024-03-22T02:06:31Z","timestamp":1711073191000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11786-024-00577-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,23]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3]]}},"alternative-id":["577"],"URL":"https:\/\/doi.org\/10.1007\/s11786-024-00577-y","relation":{},"ISSN":["1661-8270","1661-8289"],"issn-type":[{"type":"print","value":"1661-8270"},{"type":"electronic","value":"1661-8289"}],"subject":[],"published":{"date-parts":[[2024,2,23]]},"assertion":[{"value":"26 July 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 December 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 February 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"3"}}