{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,8,27]],"date-time":"2023-08-27T13:39:11Z","timestamp":1693143551882},"reference-count":14,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2010,12]]},"abstract":"<jats:p> Polynomial equation systems arising from real applications often have associated combinatorial information, expressible as graphs and underlying matroids. To simplify the system and improve its numerical robustness before attempting to solve it with numeric-algebraic techniques, solvers can employ graph algorithms to extract substructures satisfying or optimizing various combinatorial properties. When there are underlying matroids, these algorithms can be greedy and efficient. In practice, correct and effective merging of the outputs of different graph algorithms to simultaneously satisfy their goals is a key challenge. <\/jats:p><jats:p> This paper merges and improves two highly effective but separate graph-based algorithms that preprocess systems for resolving the relative position and orientation of a collection of incident rigid bodies. Such collections naturally arise in many situations, for example in the recombination of decomposed large geometric constraint systems. Each algorithm selects a subset of incidences, one to optimize algebraic complexity of a parametrized system, the other to obtain a well-formed system that is robust against numerical errors. Both algorithms are greedy and can be proven correct by revealing underlying matroids. The challenge is that the output of the first algorithm is not guaranteed to be extensible to a well-formed system, while the output of the second may not have optimal algebraic complexity. Here we show how to reconcile the two algorithms by revealing well-behaved maps between the associated matroids. <\/jats:p>","DOI":"10.1142\/s0218195910003463","type":"journal-article","created":{"date-parts":[[2011,1,4]],"date-time":"2011-01-04T00:43:19Z","timestamp":1294101799000},"page":"631-651","source":"Crossref","is-referenced-by-count":3,"title":["RECONCILING CONFLICTING COMBINATORIAL PREPROCESSORS FOR GEOMETRIC CONSTRAINT SYSTEMS"],"prefix":"10.1142","volume":"20","author":[{"given":"MEERA","family":"SITHARAM","sequence":"first","affiliation":[{"name":"CISE, University of Florida, Gainesville, Florida 32611, USA"}]},{"given":"YONG","family":"ZHOU","sequence":"additional","affiliation":[{"name":"CISE, University of Florida, Gainesville, Florida 32611, USA"}]},{"given":"J\u00d6RG","family":"PETERS","sequence":"additional","affiliation":[{"name":"CISE, University of Florida, Gainesville, Florida 32611, USA"}]}],"member":"219","published-online":{"date-parts":[[2012,4,30]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718881"},{"key":"rf3","author":"Emiris I. Z.","journal-title":"Int. J. Quant. Chem."},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1137\/0613024"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1090\/gsm\/002"},{"key":"rf7","volume":"31","author":"Hoffmann C. M.","journal-title":"J. Symb. Comput."},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195906002117"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/j.aam.2005.03.004"},{"key":"rf10","volume-title":"Solving Geometric Constraint Systems","author":"Kramer G.","year":"1992"},{"key":"rf14","volume":"115","author":"Raghavan M.","journal-title":"J. Mech. Design, Trans. ASME"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1007\/s00371-007-0184-x"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1016\/0010-4485(90)90039-F"},{"key":"rf19","first-page":"591","volume":"16","author":"Sitharam M.","journal-title":"IJCGA"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2010.01.011"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1016\/S1077-3169(02)00018-7"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195910003463","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T03:36:22Z","timestamp":1565148982000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195910003463"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,12]]},"references-count":14,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2012,4,30]]},"published-print":{"date-parts":[[2010,12]]}},"alternative-id":["10.1142\/S0218195910003463"],"URL":"https:\/\/doi.org\/10.1142\/s0218195910003463","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,12]]}}}