{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,4]],"date-time":"2026-10-04T18:16:22Z","timestamp":1791137782517,"version":"4.1.0"},"reference-count":33,"publisher":"ASME International","issue":"4","content-domain":{"domain":["asmedigitalcollection.asme.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2012,12,1]]},"abstract":"<jats:p>Current parametric CAD systems are based on solving equality types of constraints between geometric objects and parameters. This includes algebraic equations constraining the values of variables, and geometric constraints constraining the positions of geometric objects. However, to truly represent design intent, next-generation CAD systems must also allow users to input other types of constraints such as inequality constraints. Inequality constraints are expressed as inequality expressions on variables, or as geometric constraints that force geometric objects to be on specific sides or have specific orientations with respect to other objects. The research presented here investigates whether the frontier algorithm can be extended to solve geometry positioning problems involving systems of equality- and inequality-based declarations in which the inequality-based declarations are used as solution selectors to choose from multiple solutions inherently arising when solving these systems. It is found that these systems can be decomposed by the frontier algorithm in a manner similar to purely equality-based constraint systems, however they require tracking and iterating through multiple solutions and in many cases may require backtracking through the solution sequence. The computational complexity of the new algorithm is found to be the same as the frontier algorithm in the planning phase and linear in the execution phase with respect to the size of the problem but exponential with respect to the distance of solution selection steps from the satisfaction steps they control.<\/jats:p>","DOI":"10.1115\/1.4007403","type":"journal-article","created":{"date-parts":[[2012,9,18]],"date-time":"2012-09-18T22:07:20Z","timestamp":1348006040000},"update-policy":"https:\/\/doi.org\/10.1115\/crossmarkpolicy-asme","source":"Crossref","is-referenced-by-count":2,"title":["Geometric Constraint Solving With Solution Selectors"],"prefix":"10.1115","volume":"12","author":[{"given":"Bernhard","family":"Bettig","sequence":"first","affiliation":[{"name":"Department of Mechanical Engineering, West Virginia University Institute of Technology, Montgomery, WV 25136 e-mail:"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vaibhav","family":"Kale","sequence":"additional","affiliation":[{"name":"Mechanical Engineering-Engineering Mechanics Department, Michigan Technological University, Houghton, MI 49931 e-mail:"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"33","published-online":{"date-parts":[[2012,9,18]]},"reference":[{"issue":"3","key":"2019100315104143800_B1","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1115\/1.1587749","article-title":"Solution Selectors: A User-Oriented Answer to the Multiple Solution Problem in Constraint Solving","volume":"125","year":"2003","journal-title":"Trans. ASME J. Mech. Des."},{"issue":"4","key":"2019100315104143800_B2","doi-asserted-by":"crossref","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","year":"2001","journal-title":"J. Symb. Comput."},{"issue":"4","key":"2019100315104143800_B3","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1016\/S0010-4485(03)00099-X","article-title":"Making Constraint Solvers More Usable: Overconstraint Problem","volume":"36","year":"2004","journal-title":"Comput.-Aided Des."},{"key":"2019100315104143800_B4","article-title":"MAE455: Computer Aided Design and Drafting Course Notes","year":"2011"},{"issue":"5","key":"2019100315104143800_B5","doi-asserted-by":"crossref","first-page":"655","DOI":"10.1080\/16864360.2005.10738330","article-title":"A Brief on Constraint Solving","volume":"2","year":"2005","journal-title":"Comput.-Aided Des. Appl."},{"key":"2019100315104143800_B6","unstructured":"Fudos, I., 1995, \u201cConstraint Solving for Computer Aided Design,\u201d Ph.D. thesis, Purdue University, West Lafayette, IN."},{"key":"2019100315104143800_B7","unstructured":"Hsu, C., 1996, \u201cGraph-Based Approach for Solving Geometric Constraint Problems,\u201d Ph.D. thesis, Department of Computer Science, University of Utah, Salt Lake City, UT."},{"key":"2019100315104143800_B8","unstructured":"Lomonosov, A., 2004, \u201cGraph and Combinatorial Algorithms for Geometric Constraint Solving,\u201d Doctoral Dissertation, University of Florida, Gainesville, FL."},{"issue":"5","key":"2019100315104143800_B9","first-page":"309","article-title":"Interactive Design of 3D Models With Geometric Constraints","volume":"7","year":"1991","journal-title":"Visual Comput."},{"key":"2019100315104143800_B10","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/978-3-642-78114-8_4","article-title":"A System for Constructive Constraint-Based Modeling","volume-title":"Modeling in Computer Graphics Methods and Applications","year":"1993"},{"key":"2019100315104143800_B11","volume-title":"Solving Geometric Constraint Systems: A Case Study in Kinematics","year":"1992"},{"issue":"4","key":"2019100315104143800_B12","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1142\/S0218195996000253","article-title":"Correctness Proof of a Geometric Constraint Solver","volume":"6","year":"1996","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"2","key":"2019100315104143800_B13","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1145\/248210.248223","article-title":"A Graph-Constructive Approach to Solving Systems of Geometric Constraints","volume":"16","year":"1997","journal-title":"ACM Trans. Graphics"},{"issue":"3","key":"2019100315104143800_B14","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/0010-4485(88)90019-X","article-title":"Variation of Geometrics Based on a Geometric-Reasoning Method","volume":"20","year":"1988","journal-title":"Comput.-Aided Des."},{"key":"2019100315104143800_B15","doi-asserted-by":"crossref","unstructured":"Shimizu, S., Inoue, K., and Numao, M., 1991, \u201cAn ATMS-Based Geometric Constraint Solver for 3D CAD,\u201d Tools for Artificial Intelligence, TAI'91, Third International Conference on, pp. 282\u2013290.","DOI":"10.1109\/TAI.1991.167106"},{"issue":"2","key":"2019100315104143800_B16","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/0097-8493(90)90033-T","article-title":"Geometric Constraints and Reasoning for Geometrical CAD Systems","volume":"14","year":"1990","journal-title":"Comput. Graph."},{"issue":"12","key":"2019100315104143800_B17","doi-asserted-by":"crossref","first-page":"741","DOI":"10.1016\/0010-4485(93)90101-S","article-title":"Constraint Definition System: A Computer-Algebra Based Approach to Solving Geometric-Constraint Problems","volume":"25","year":"1993","journal-title":"Comput.-Aided Des."},{"issue":"6","key":"2019100315104143800_B18","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1016\/0010-4485(94)00013-4","article-title":"Geometric Constraint Solver","volume":"27","year":"1995","journal-title":"Comput.-Aided Des."},{"key":"2019100315104143800_B19","doi-asserted-by":"crossref","unstructured":"Sohrt, W., and Br\u00fcderlin, B. D., 1991, \u201cInteraction With Constraints in 3D Modeling,\u201d Proceedings of the First ACM Symposium on Solid Modeling Foundations and CAD\/CAM Applications, pp. 387\u2013396.","DOI":"10.1145\/112515.112570"},{"issue":"3","key":"2019100315104143800_B20","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1142\/S0218195905001701","article-title":"An Efficient Method to Determine the Intended Solution for a System of Geometric Constraints","volume":"15","year":"2005","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"1","key":"2019100315104143800_B21","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/S0097-8493(02)00243-1","article-title":"Genetic Algorithms for Root Multiselection in Constructive Geometric Constraint Solving","volume":"27","year":"2003","journal-title":"Comput. Graphics"},{"issue":"5","key":"2019100315104143800_B22","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1006\/jsco.2000.0392","article-title":"A Systematic Framework for Solving Geometric Constraints Analytically","volume":"30","year":"2000","journal-title":"J. Symb. Comput."},{"issue":"1","key":"2019100315104143800_B23","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1016\/S0004-3702(00)00061-8","article-title":"Sketch-Based Pruning of a Solution Space Within a Formal Geometric Constraint Solver","volume":"124","year":"2000","journal-title":"Artif. Intell."},{"key":"2019100315104143800_B24","doi-asserted-by":"crossref","unstructured":"Essert-Villard, C., 2002, \u201cHelping the Designer in Solution Selection: Applications in CAD,\u201d Proceedings of the International Conference on Computational Science-Part II, pp. 151\u2013160.","DOI":"10.1007\/3-540-46080-2_16"},{"issue":"2","key":"2019100315104143800_B25","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1145\/1138450.1138452","article-title":"Solution Space Navigation for Geometric Constraint Systems","volume":"25","year":"2006","journal-title":"ACM Trans. Graphics"},{"issue":"4","key":"2019100315104143800_B26","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1006\/jsco.2000.0403","article-title":"Decomposition Plans for Geometric Constraint Problems, Part II: New Algorithms","volume":"31","year":"2001","journal-title":"J. Symb. Comput."},{"key":"2019100315104143800_B27","unstructured":"Chaubal, S., \u201cImplementation of Modified Frontier Algorithm for Constraint Solving,\u201d Masters Thesis, Michigan Technological University, Houghton, MI."},{"key":"2019100315104143800_B28","year":"2007"},{"key":"2019100315104143800_B29","doi-asserted-by":"crossref","unstructured":"Hoffmann, C. M., Lomonosov, A., and Sitharam, M., 1997, \u201cFinding Solvable Subsets of Constraint Graphs,\u201d Proceedings Principles and Practice of Constraint Programming-CP97: Third International Conference, CP'97, Linz, Austria, Oct. 29\u2013Nov. 1.","DOI":"10.1007\/BFb0017460"},{"key":"2019100315104143800_B30","year":"2003"},{"issue":"1","key":"2019100315104143800_B31","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1007\/s00366-006-0025-y","article-title":"Integrating Multiple Information Representations in a Single CAD\/CAM\/CAE Environment","volume":"22","year":"2006","journal-title":"Eng. Comput."},{"issue":"8","key":"2019100315104143800_B32","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1016\/S0965-9978(99)00009-5","article-title":"An Object-Oriented Program Shell for Integrating CAD Software Tools","volume":"30","year":"1999","journal-title":"Adv. Eng. Software"},{"issue":"17","key":"2019100315104143800_B33","doi-asserted-by":"crossref","first-page":"2945","DOI":"10.1002\/(SICI)1097-0207(19960915)39:17<2945::AID-NME984>3.0.CO;2-X","article-title":"An Object-Oriented Framework for Interactive Numerical Analysis in a Graphical User Interface Environment","volume":"39","year":"1996","journal-title":"Int. J. Numer. Methods Eng."}],"container-title":["Journal of Computing and Information Science in Engineering"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/asmedigitalcollection.asme.org\/computingengineering\/article-pdf\/doi\/10.1115\/1.4007403\/6098147\/jcis_12_4_041002.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/asmedigitalcollection.asme.org\/computingengineering\/article-pdf\/doi\/10.1115\/1.4007403\/6098147\/jcis_12_4_041002.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T00:45:32Z","timestamp":1744159532000},"score":1,"resource":{"primary":{"URL":"https:\/\/asmedigitalcollection.asme.org\/computingengineering\/article\/doi\/10.1115\/1.4007403\/371318\/Geometric-Constraint-Solving-With-Solution"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,9,18]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,12,1]]}},"URL":"https:\/\/doi.org\/10.1115\/1.4007403","relation":{},"ISSN":["1530-9827","1944-7078"],"issn-type":[{"value":"1530-9827","type":"print"},{"value":"1944-7078","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,9,18]]},"article-number":"041002"}}