{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T01:59:11Z","timestamp":1760061551040},"reference-count":25,"publisher":"World Scientific Pub Co Pte Ltd","issue":"04n05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2013,8]]},"abstract":"<jats:p>We design an algorithm to compute the Newton polytope of the resultant, known as resultant polytope, or its orthogonal projection along a given direction. The resultant is fundamental in algebraic elimination, optimization, and geometric modeling. Our algorithm exactly computes vertex- and halfspace-representations of the polytope using an oracle producing resultant vertices in a given direction, thus avoiding walking on the polytope whose dimension is \u03b1 - n - 1, where the input consists of \u03b1 points in \u2124<jats:sup>n<\/jats:sup>. Our approach is output-sensitive as it makes one oracle call per vertex and per facet. It extends to any polytope whose oracle-based definition is advantageous, such as the secondary and discriminant polytopes. Our publicly available implementation uses the experimental CGAL package triangulation. Our method computes 5-, 6- and 7- dimensional polytopes with 35K, 23K and 500 vertices, respectively, within 2hrs, and the Newton polytopes of many important surface equations encountered in geometric modeling in &lt; 1sec, whereas the corresponding secondary polytopes are intractable. It is faster than tropical geometry software up to dimension 5 or 6. Hashing determinantal predicates accelerates execution up to 100 times. One variant computes inner and outer approximations with, respectively, 90% and 105% of the true volume, up to 25 times faster.<\/jats:p>","DOI":"10.1142\/s0218195913600108","type":"journal-article","created":{"date-parts":[[2014,7,9]],"date-time":"2014-07-09T03:05:28Z","timestamp":1404875128000},"page":"397-423","source":"Crossref","is-referenced-by-count":8,"title":["AN ORACLE-BASED, OUTPUT-SENSITIVE ALGORITHM FOR PROJECTIONS OF RESULTANT POLYTOPES"],"prefix":"10.1142","volume":"23","author":[{"given":"IOANNIS Z.","family":"EMIRIS","sequence":"first","affiliation":[{"name":"Department of Informatics and Telecommunications, University of Athens, Athens, 15784, Greece"}]},{"given":"VISSARION","family":"FISIKOPOULOS","sequence":"additional","affiliation":[{"name":"Department of Informatics and Telecommunications, University of Athens, Athens, 15784, Greece"}]},{"given":"CHRISTOS","family":"KONAXIS","sequence":"additional","affiliation":[{"name":"Archimedes Center for Modeling, Analysis and Computation (ACMAC), University of Crete, Heraklio, 71409, Greece"}]},{"given":"LUIS","family":"PE\u00d1ARANDA","sequence":"additional","affiliation":[{"name":"IMPA \u2013 Instituto Nacional de Matem\u00e1tica Pura e Aplicada, Rio de Janeiro, 22460-320, Brazil"}]}],"member":"219","published-online":{"date-parts":[[2014,7,8]]},"reference":[{"key":"p_1","first-page":"81","volume":"479","author":"Emiris I. Z.","year":"2013","journal-title":"Theor. Comp. Sci. Special Issue on Symbolic & Numeric Comput."},{"key":"p_2","first-page":"111","author":"Sturmfels B.","year":"2008","journal-title":"New York"},{"key":"p_3","first-page":"330","author":"Rambau J.","year":"2002","journal-title":"Beijing"},{"key":"p_4","first-page":"45","volume":"2012","author":"Emiris I. Z.","year":"2013","journal-title":"Special Issue on Symposium Solid and Phys. Modeling"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2012.03.008"},{"key":"p_7","first-page":"287","volume":"2013","author":"Jensen A.","journal-title":"J. Algebra."},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022497624378"},{"key":"p_10","first-page":"173","author":"Dickenstein A.","year":"2013","journal-title":"Proc. ACM Int. Symp. Symbolic & Algebraic Comput."},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.1070\/RM1999v054n05ABEH000213"},{"key":"p_12","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195902000980"},{"key":"p_13","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009506"},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009439"},{"key":"p_15","first-page":"245","author":"Huggins P.","year":"2006","journal-title":"Berlin"},{"key":"p_16","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0185-3"},{"issue":"1","key":"p_17","first-page":"173","volume":"210","author":"Br\u00f6nnimann H.","year":"1999","journal-title":"Spec. Issue on Real Numbers and Computers"},{"key":"p_18","first-page":"40","author":"Dumas J.-G.","year":"2002","journal-title":"Beijing"},{"key":"p_20","first-page":"179","author":"Emiris I. Z.","year":"2012","journal-title":"Proc. Annual ACM Symp. Computational Geometry"},{"key":"p_24","doi-asserted-by":"publisher","DOI":"10.1007\/BF01459245"},{"key":"p_26","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1145\/1542362.1542403","author":"Boissonnat J.-D.","year":"2009","journal-title":"Proc. Annual ACM Symp. Computational Geometry"},{"key":"p_28","first-page":"443","author":"Fisikopoulos V.","year":"2012","journal-title":"Springer"},{"key":"p_31","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(93)90009-U"},{"key":"p_32","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1145\/378583.378673","author":"Gawrilow E.","year":"2001","journal-title":"Proc. Annual ACM Symp. Computational Geometry"},{"key":"p_35","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(96)00023-5"},{"key":"p_36","first-page":"165","author":"Br\u00f6nnimann H.","year":"1998","journal-title":"Proc. Annual ACM Symp. Computational Geometry"},{"key":"p_38","first-page":"26","author":"Bremner D.","year":"1996","journal-title":"UK"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195913600108","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,15]],"date-time":"2023-07-15T02:53:54Z","timestamp":1689389634000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195913600108"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,8]]},"references-count":25,"journal-issue":{"issue":"04n05","published-online":{"date-parts":[[2014,7,8]]},"published-print":{"date-parts":[[2013,8]]}},"alternative-id":["10.1142\/S0218195913600108"],"URL":"https:\/\/doi.org\/10.1142\/s0218195913600108","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,8]]}}}