{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,19]],"date-time":"2025-11-19T15:00:00Z","timestamp":1763564400522,"version":"3.41.2"},"reference-count":35,"publisher":"ASME International","issue":"8","license":[{"start":{"date-parts":[[2025,4,16]],"date-time":"2025-04-16T00:00:00Z","timestamp":1744761600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.asme.org\/publications-submissions\/publishing-information\/legal-policies"}],"content-domain":{"domain":["asmedigitalcollection.asme.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,8,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Identifying and eliminating conflicts and redundancies between geometric constraints is crucial for effective constraint resolving in engineering design. This research proposes a graph-based conflict detection and resolution scheme for geometric constraint systems with both equality and inequality constraints based on numerical methods using a pruning and backtracking strategy. Initially, the minimum subset of conflicting constraints is detected by traversing all connected subgraphs of the original constraint graph in a pruning manner. The traversal process is encoded in a directed acyclic graph (DAG). The solvability of each constraint subgraph is determined by solving its equivalent algebraic system using variants of the Levenberg\u2013Marquardt (LM) algorithm (Ma, 2008, \u201cA Globally Convergent Levenberg\u2013Marquardt Method for the Least l2-Norm Solution of Nonlinear Inequalities,\u201d Appl. Math. Comput., 206(1), pp. 133\u2013140; Amini et al., 2018, \u201cAn Efficient Levenberg\u2013Marquardt Method With a New LM Parameter for Systems of Nonlinear Equations,\u201d Optimization, 67(5), pp. 637\u2013650) and verifying the solution. Inconsistencies between conflicting constraints are eliminated by modifying or discarding constraints recommended by a set of criteria. Finally, the resolution is validated by backtracking ancestor subgraphs along the paths of the DAG. Experimental results demonstrate the effectiveness of the proposed framework in handling inconsistent overconstrainedness between geometric constraints in various parametric forms, including those arising from violations of geometric rules or theorems.<\/jats:p>","DOI":"10.1115\/1.4068260","type":"journal-article","created":{"date-parts":[[2025,3,20]],"date-time":"2025-03-20T13:49:50Z","timestamp":1742478590000},"update-policy":"https:\/\/doi.org\/10.1115\/crossmarkpolicy-asme","source":"Crossref","is-referenced-by-count":1,"title":["An Efficient Conflict Detection and Resolution Scheme for Geometric Constraints Using a Pruning and Backtracking Strategy"],"prefix":"10.1115","volume":"25","author":[{"given":"Anyu","family":"Mu","sequence":"first","affiliation":[{"name":"Zhejiang University State Key Lab of CAD&CG, School of Mechanical Engineering, , \u00a0 ,","place":["Hangzhou, China, 310027"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhenyu","family":"Liu","sequence":"additional","affiliation":[{"name":"Zhejiang University State Key Lab of CAD&CG, School of Mechanical Engineering, , \u00a0 ,","place":["Hangzhou, China, 310027"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guifang","family":"Duan","sequence":"additional","affiliation":[{"name":"Zhejiang University State Key Lab of CAD&CG, School of Mechanical Engineering, , \u00a0 ,","place":["Hangzhou, China, 310027"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianrong","family":"Tan","sequence":"additional","affiliation":[{"name":"Zhejiang University State Key Lab of CAD&CG, School of Mechanical Engineering, , \u00a0 ,","place":["Hangzhou, China, 310027"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"33","published-online":{"date-parts":[[2025,4,16]]},"reference":[{"issue":"2","key":"2025041607443656400_CIT0001","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/S0965-9978(02)00108-4","article-title":"A Hybrid Approach to Geometric Constraint Solving With Graph Analysis and Reduction","volume":"34","author":"Lee","year":"2003","journal-title":"Adv. Eng. Software"},{"issue":"4","key":"2025041607443656400_CIT0002","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1145\/1964921.1964947","article-title":"GlobFit: Consistently Fitting Primitives by Discovering Global Relations","volume":"30","author":"Li","year":"2011","journal-title":"ACM Trans. Graphics"},{"key":"2025041607443656400_CIT0003","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1016\/j.cag.2019.05.028","article-title":"Real-Time Editing of Man-Made Mesh Models Under Geometric Constraints","volume":"82","author":"Zhang","year":"2019","journal-title":"Comput. Graphics"},{"issue":"4","key":"2025041607443656400_CIT0004","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0010-4485(96)88488-0","article-title":"Algorithms for the Structural Diagnosis and Decomposition of Sparse, Underconstrained Design Systems","volume":"28","author":"Sridhar","year":"1996","journal-title":"Comput. Aided Des."},{"issue":"4","key":"2025041607443656400_CIT0005","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0010-4485(82)90292-5","article-title":"Modification of Geometric Models Through Variational Geometry","volume":"14","author":"Light","year":"1982","journal-title":"Comput. Aided Des."},{"key":"2025041607443656400_CIT0006","first-page":"143","article-title":"Numerical Decomposition of Geometric Constraints","author":"Foufou","year":"2005"},{"issue":"4","key":"2025041607443656400_CIT0007","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1016\/j.cad.2006.01.005","article-title":"Geometric Constraint Solving: The Witness Configuration Method","volume":"38","author":"Michelucci","year":"2006","journal-title":"Comput. Aided Des."},{"issue":"4","key":"2025041607443656400_CIT0008","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jsco.2000.0402","article-title":"Decomposition Plans for Geometric Constraint Systems, Part I: Performance Measures for CAD","volume":"31","author":"Hoffman","year":"2001","journal-title":"J. Symb. Comput."},{"issue":"4","key":"2025041607443656400_CIT0009","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1006\/jsco.2000.0403","article-title":"Decomposition Plans for Geometric Constraint Problems, Part II: New Algorithms","volume":"31","author":"Hoffman","year":"2001","journal-title":"J. Symb. Comput."},{"issue":"5","key":"2025041607443656400_CIT0010","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1142\/S0218195906002105","article-title":"Decomposition of Geometric Constraint Systems: A Survey","volume":"16","author":"Jermann","year":"2006","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"2025041607443656400_CIT0011","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1007\/978-0-387-35187-2_33","volume-title":"Product Modeling for Computer Integrated Design and Manufacture IFIP Advances in Information and Communication Technology","author":"Joan-Arinyo","year":"1997"},{"issue":"5","key":"2025041607443656400_CIT0012","doi-asserted-by":"publisher","first-page":"599","DOI":"10.1016\/S0097-8493(97)00038-1","article-title":"A Correct Rule-Based Geometric Constraint Solver","volume":"21","author":"Joan-Arinyo","year":"1997","journal-title":"Comput. Graphics"},{"year":"2014","author":"Ait-Aoudia","key":"2025041607443656400_CIT0013"},{"key":"2025041607443656400_CIT0014","first-page":"463","article-title":"Finding Solvable Subsets of Constraint Graphs","author":"Hoffmann","year":"1997"},{"key":"2025041607443656400_CIT0015","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1016\/j.cad.2017.05.019","article-title":"Over-Constraints Detection and Resolution in Geometric Equation Systems","volume":"90","author":"Hu","year":"2017","journal-title":"Comput. Aided Des."},{"key":"2025041607443656400_CIT0016","doi-asserted-by":"publisher","first-page":"101087","DOI":"10.1016\/j.aei.2020.101087","article-title":"A Decision-Support Method for Information Inconsistency Resolution in Direct Modeling of CAD Models","volume":"44","author":"Zou","year":"2020","journal-title":"Adv. Eng. Inf."},{"issue":"9","key":"2025041607443656400_CIT0017","doi-asserted-by":"publisher","first-page":"770","DOI":"10.1016\/j.advengsoft.2007.10.003","article-title":"Dealing With Redundancy and Inconsistency in Constructive Geometric Constraint Solving","volume":"39","author":"Podgorelec","year":"2008","journal-title":"Adv. Eng. Software"},{"issue":"1","key":"2025041607443656400_CIT0018","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/j.amc.2008.08.039","article-title":"A Globally Convergent Levenberg\u2013Marquardt Method for the Least l2-Norm Solution of Nonlinear Inequalities","volume":"206","author":"Ma","year":"2008","journal-title":"Appl. Math. Comput."},{"issue":"5","key":"2025041607443656400_CIT0019","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1080\/02331934.2018.1435655","article-title":"An Efficient Levenberg\u2013Marquardt Method With a New LM Parameter for Systems of Nonlinear Equations","volume":"67","author":"Amini","year":"2018","journal-title":"Optimization"},{"key":"2025041607443656400_CIT0020","doi-asserted-by":"crossref","DOI":"10.2307\/j.ctvcm4hcj","volume-title":"Nonlinear Optimization","author":"Ruszczynski","year":"2011"},{"key":"2025041607443656400_CIT0021","first-page":"1","volume-title":"Springer Series in Operations Research and Financial Engineering","author":"Nocedal","year":"2006"},{"key":"2025041607443656400_CIT0022","first-page":"625","article-title":"A Modified Levenberg\u2013Marquardt Algorithm for Singular System of Nonlinear Equations","volume":"21","author":"Fan","year":"2003","journal-title":"J. Comput. Math."},{"issue":"2","key":"2025041607443656400_CIT0023","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/BF00935547","article-title":"Solving Nonlinear Inequalities in a Finite Number of Iterations","volume":"33","author":"Mayne","year":"1981","journal-title":"J. Optim. Theory Appl."},{"issue":"2","key":"2025041607443656400_CIT0024","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/BF01390421","article-title":"On the Solution of Nonlinear Inequalities in a Finite Number of Iterations","volume":"46","author":"Sahba","year":"1985","journal-title":"Numer. Math."},{"issue":"5","key":"2025041607443656400_CIT0025","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1007\/BF01436488","article-title":"Newton\u2019s Method for Nonlinear Inequalities","volume":"21","author":"Daniel","year":"1973","journal-title":"Numer. Math."},{"issue":"1","key":"2025041607443656400_CIT0026","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1007\/BF01584250","article-title":"A Global Quadratic Algorithm for Solving a System of Mixed Equalities and Inequalities","volume":"21","author":"Garcia-Palomares","year":"1981","journal-title":"Math. Program."},{"issue":"2","key":"2025041607443656400_CIT0027","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF00249052","article-title":"A Class of Smoothing Functions for Nonlinear and Mixed Complementarity Problems","volume":"5","author":"Chen","year":"1996","journal-title":"Comput. Optim. Appl."},{"issue":"1","key":"2025041607443656400_CIT0028","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/S0377-0427(00)00541-0","article-title":"Solving Variational Inequality Problems via Smoothing-Nonsmooth Reformulations","volume":"129","author":"Sun","year":"2001","journal-title":"J. Comput. Appl. Math."},{"issue":"10","key":"2025041607443656400_CIT0029","doi-asserted-by":"publisher","first-page":"3056","DOI":"10.1016\/j.amc.2010.04.025","article-title":"A Smoothing Self-Adaptive Levenberg\u2013Marquardt Algorithm for Solving System of Nonlinear Inequalities","volume":"216","author":"He","year":"2010","journal-title":"Appl. Math. Comput."},{"article-title":"Pessimistic Decision Tree Pruning Based on Tree Size","year":"1997","author":"Mansour","key":"2025041607443656400_CIT0030"},{"key":"2025041607443656400_CIT0031","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1093\/acprof:oso\/9780199206650.003.0006","volume-title":"Networks: An Introduction","author":"Newman","year":"2010"},{"key":"2025041607443656400_CIT0032","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/j.cad.2013.11.002","article-title":"Defining Tools to Address Over-Constrained Geometric Problems in Computer Aided Design","volume":"48","author":"Moinet","year":"2014","journal-title":"Comput. Aided Des."},{"issue":"2","key":"2025041607443656400_CIT0033","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1111\/j.1467-8659.2007.01016.x","article-title":"Efficient RANSAC for Point-Cloud Shape Detection","volume":"26","author":"Schnabel","year":"2007","journal-title":"Comput. Graphics Forum"},{"key":"2025041607443656400_CIT0034","doi-asserted-by":"publisher","first-page":"103780","DOI":"10.1016\/j.cad.2024.103780","article-title":"Structural Regularity Detection and Enhancement for Surface Mesh Reconstruction in Reverse Engineering","volume":"177","author":"Mu","year":"2024","journal-title":"Comput. Aided Des."},{"issue":"3","key":"2025041607443656400_CIT0035","doi-asserted-by":"publisher","first-page":"897","DOI":"10.1007\/s10489-014-0560-y","article-title":"Conflict-Based Pruning of a Solution Space Within a Constructive Geometric Constraint Solver","volume":"41","author":"Yeguas","year":"2014","journal-title":"Appl. Intell."}],"container-title":["Journal of Computing and Information Science in Engineering"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/asmedigitalcollection.asme.org\/computingengineering\/article-pdf\/25\/8\/084501\/7448216\/jcise-24-1570.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/asmedigitalcollection.asme.org\/computingengineering\/article-pdf\/25\/8\/084501\/7448216\/jcise-24-1570.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,16]],"date-time":"2025-04-16T11:44:42Z","timestamp":1744803882000},"score":1,"resource":{"primary":{"URL":"https:\/\/asmedigitalcollection.asme.org\/computingengineering\/article\/25\/8\/084501\/1213917\/An-Efficient-Conflict-Detection-and-Resolution"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,16]]},"references-count":35,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2025,8,1]]}},"URL":"https:\/\/doi.org\/10.1115\/1.4068260","relation":{},"ISSN":["1530-9827","1944-7078"],"issn-type":[{"type":"print","value":"1530-9827"},{"type":"electronic","value":"1944-7078"}],"subject":[],"published":{"date-parts":[[2025,4,16]]},"article-number":"084501"}}