{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T08:15:57Z","timestamp":1759133757040,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2006,4,1]],"date-time":"2006-04-01T00:00:00Z","timestamp":1143849600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2006,4]]},"abstract":"<jats:p>We study the well documented problem of systematically navigating the potentially exponentially many roots or realizations of well-constrained, variational geometric constraint systems. We give a scalable method called the Equation and Solution Manager (ESM) that can be used both for automatic searches and visual, user-driven searches for desired realizations. The method incrementally assembles the desired solution of the entire system and avoids combinatorial explosion by offering the user a visual walk-through of the solutions to recursively constructed subsystems and by permitting the user to make gradual, adaptive solution choices.We isolate requirements on companion methods that are essential and desirable for efficient, meaningful solution space navigation. Specifically, they permit (a) incorporation of many existing approaches to solution space steering or navigation into the ESM; and (b) integration of the ESM into a standard geometric constraint solver architecture. We address the latter challenge and explain how the integration is achieved. Additionally, we sketch the ESM implementation as part of an opensource, 2D and 3D geometric constraint solver, FRONTIER.<\/jats:p>","DOI":"10.1145\/1138450.1138452","type":"journal-article","created":{"date-parts":[[2006,7,25]],"date-time":"2006-07-25T14:14:26Z","timestamp":1153836866000},"page":"194-213","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Solution space navigation for geometric constraint systems"],"prefix":"10.1145","volume":"25","author":[{"given":"Meera","family":"Sitharam","sequence":"first","affiliation":[{"name":"University of Florida, Gainesville, FL"}]},{"given":"Adam","family":"Arbree","sequence":"additional","affiliation":[{"name":"University of Florida, Gainesville, FL"}]},{"given":"Yong","family":"Zhou","sequence":"additional","affiliation":[{"name":"University of Florida, Gainesville, FL"}]},{"given":"Naganandhini","family":"Kohareswaran","sequence":"additional","affiliation":[{"name":"University of Florida, Gainesville, FL"}]}],"member":"320","published-online":{"date-parts":[[2006,4]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"445","article-title":"Solution selectors: A user oriented answer to the multiple solution problem in constraint solving","volume":"125","author":"Bettig B.","year":"2003","unstructured":"Bettig , B. and Shah , A. 2003 . Solution selectors: A user oriented answer to the multiple solution problem in constraint solving . J. Mechan. Design 125 , 3, 445 -- 451 .]] Bettig, B. and Shah, A. 2003. Solution selectors: A user oriented answer to the multiple solution problem in constraint solving. J. Mechan. Design 125, 3, 445--451.]]","journal-title":"J. Mechan. Design"},{"key":"e_1_2_1_2_1","unstructured":"Bjorner A. Vergnas M. L. Sturmfels B. White N. and Ziegler G. 1993. Oriented Matroids. Encyclopaedia of Mathematics. vol. 46. G-C. Rota Ed. Cambridge University Press.]]  Bjorner A. Vergnas M. L. Sturmfels B. White N. and Ziegler G. 1993. Oriented Matroids. Encyclopaedia of Mathematics. vol. 46. G-C. Rota Ed. Cambridge University Press.]]"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0010-4485(94)00013-4"},{"volume-title":"ACM SIGGRAPH.","author":"Bruderlin B.","key":"e_1_2_1_4_1","unstructured":"Bruderlin , B. 1986. Constructing three-dimensional geometric object defined by constraints . In ACM SIGGRAPH. Chapel Hill, NC .]] Bruderlin, B. 1986. Constructing three-dimensional geometric object defined by constraints. In ACM SIGGRAPH. Chapel Hill, NC.]]"},{"key":"e_1_2_1_5_1","first-page":"26","article-title":"Structural rigidity","volume":"1","author":"Crapo H.","year":"1979","unstructured":"Crapo , H. 1979 . Structural rigidity . Structural Topology 1 , 26 -- 45 .]] Crapo, H. 1979. Structural rigidity. Structural Topology 1, 26--45.]]","journal-title":"Structural Topology"},{"key":"e_1_2_1_6_1","first-page":"52","article-title":"The tetrahedral-octahedral truss","volume":"7","author":"Crapo H.","year":"1982","unstructured":"Crapo , H. 1982 . The tetrahedral-octahedral truss . Structural Topology 7 , 52 -- 61 .]] Crapo, H. 1982. The tetrahedral-octahedral truss. Structural Topology 7, 52--61.]]","journal-title":"Structural Topology"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195996000253"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/248210.248223"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Graver J. E. Servatius B. and Servatius H. 1993. Combinatorial Rigidity. American Mathematical Society.]]  Graver J. E. Servatius B. and Servatius H. 1993. Combinatorial Rigidity. American Mathematical Society.]]","DOI":"10.1090\/gsm\/002"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221008"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Hoffmann C. Sitharam M. and Yuan B. 2004. Making constraint solvers more useable: the overconstraint problem. Comput. Aided Design to appear.]]  Hoffmann C. Sitharam M. and Yuan B. 2004. Making constraint solvers more useable: the overconstraint problem. Comput. Aided Design to appear.]]","DOI":"10.1016\/S0010-4485(03)00099-X"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0017460"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Hoffmann C. M. Lomonosov A. and Sitharam M. 1998a. Geometric constraint decomposition. In Geometric Constraint Solving B. Bruderlin and D. Roller Eds. Springer-Verlag.]]  Hoffmann C. M. Lomonosov A. and Sitharam M. 1998a. Geometric constraint decomposition. In Geometric Constraint Solving B. Bruderlin and D. Roller Eds. Springer-Verlag.]]","DOI":"10.1007\/978-3-642-58898-3_9"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Hoffmann C. M. Lomonosov A. and Sitharam M. 1998b. Geometric constraint decomposition. In Geometric Constraint Solving B. Bruderlin and D. Roller Eds Springer Verlag. Eds. 170--195.]]  Hoffmann C. M. Lomonosov A. and Sitharam M. 1998b. Geometric constraint decomposition. In Geometric Constraint Solving B. Bruderlin and D. Roller Eds Springer Verlag. Eds. 170--195.]]","DOI":"10.1007\/978-3-642-58898-3_9"},{"key":"e_1_2_1_17_1","volume-title":"Lecture Notes in Computer Science","volume":"1779","author":"Hoffmann C. M.","unstructured":"Hoffmann , C. M. , Lomonosov , A. , and Sitharam , M . 1999. Planning geometric constraint decompositions via graph transformations . In Lecture Notes in Computer Science , vol. 1779 . Springer Verlag, 309--324.]] Hoffmann, C. M., Lomonosov, A., and Sitharam, M. 1999. Planning geometric constraint decompositions via graph transformations. In Lecture Notes in Computer Science, vol. 1779. Springer Verlag, 309--324.]]"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.2000.0402"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.2000.0403"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0097-8493(02)00243-1"},{"volume-title":"Design of a 3d graphical user interface for frontier, a geometric constraint solver graphs. M. thesis","author":"Kohareswaran N.","key":"e_1_2_1_21_1","unstructured":"Kohareswaran , N. 2003. Design of a 3d graphical user interface for frontier, a geometric constraint solver graphs. M. thesis . University of Florida , Department of Computer and Information Science, Gainesville, FL.]] Kohareswaran, N. 2003. Design of a 3d graphical user interface for frontier, a geometric constraint solver graphs. M. thesis. University of Florida, Department of Computer and Information Science, Gainesville, FL.]]"},{"volume-title":"Solving Geometric Constraint Systems","author":"Kramer G.","key":"e_1_2_1_22_1","unstructured":"Kramer , G. 1992. Solving Geometric Constraint Systems . MIT Press .]] Kramer, G. 1992. Solving Geometric Constraint Systems. MIT Press.]]"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01534980"},{"key":"e_1_2_1_25_1","unstructured":"Lomonosov A. and Sitharam M. 2004. Graph algorithms for geometric constraint solving. Based on Lomonosov's Univ Florida PhD Thesis 2004. Submitted for publication. Available on request from sitharam@cise.ufl.edu.]]   Lomonosov A. and Sitharam M. 2004. Graph algorithms for geometric constraint solving. Based on Lomonosov's Univ Florida PhD Thesis 2004. Submitted for publication. Available on request from sitharam@cise.ufl.edu.]]"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/376957.376995"},{"key":"e_1_2_1_27_1","unstructured":"Owen J. D-cubed commercial geometric constraint solving software. www.d-cubed.co.uk\/.]]  Owen J. D-cubed commercial geometric constraint solving software. www.d-cubed.co.uk\/.]]"},{"volume-title":"an opensource 3d geometric constraint solver: algorithms and architecture. Monograph, in preparation. www.cise.ufl.edu\/~sitharam\/partone.pdf. and \/partwo.pdf.]]","author":"Sitharam M.","key":"e_1_2_1_28_1","unstructured":"Sitharam , M. 2004a. Frontier , an opensource 3d geometric constraint solver: algorithms and architecture. Monograph, in preparation. www.cise.ufl.edu\/~sitharam\/partone.pdf. and \/partwo.pdf.]] Sitharam, M. 2004a. Frontier, an opensource 3d geometric constraint solver: algorithms and architecture. Monograph, in preparation. www.cise.ufl.edu\/~sitharam\/partone.pdf. and \/partwo.pdf.]]"},{"key":"e_1_2_1_29_1","volume-title":"opensource gnu geometric constraint solver: Version 1 (2001) for general 2d systems","author":"Sitharam M.","year":"2002","unstructured":"Sitharam , M. 2004b. Frontier , opensource gnu geometric constraint solver: Version 1 (2001) for general 2d systems ; version 2 ( 2002 ) for 2d and some 3d systems; version 3 (2003) for general 2d and 3d systems. In http:\/\/www.cise.ufl.edu\/~sitharam, http:\/\/www.gnu.org.]] Sitharam, M. 2004b. Frontier, opensource gnu geometric constraint solver: Version 1 (2001) for general 2d systems; version 2 (2002) for 2d and some 3d systems; version 3 (2003) for general 2d and 3d systems. In http:\/\/www.cise.ufl.edu\/~sitharam, http:\/\/www.gnu.org.]]"},{"volume-title":"AMS-DIMACS (volume on Computer Aided Design and Manufacturing)","author":"Sitharam M.","key":"e_1_2_1_30_1","unstructured":"Sitharam , M. 2004c. Combinatorial approaches to geometric constraint solving: problems, progress and directions . In AMS-DIMACS (volume on Computer Aided Design and Manufacturing) , D. Dutta, R. Janardhan, and M. Smid, Eds. vol. 67 , 117--163.]] Sitharam, M. 2004c. Combinatorial approaches to geometric constraint solving: problems, progress and directions. In AMS-DIMACS (volume on Computer Aided Design and Manufacturing), D. Dutta, R. Janardhan, and M. Smid, Eds. vol. 67, 117--163.]]"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2005.05.001"},{"key":"e_1_2_1_32_1","unstructured":"Sitharam M. Peters J. and Zhou Y. 2004. Solving minimal wellconstrained 3d geometric constraint systems: combinatorial optimization of algebraic complexity.]]  Sitharam M. Peters J. and Zhou Y. 2004. Solving minimal wellconstrained 3d geometric constraint systems: combinatorial optimization of algebraic complexity.]]"},{"key":"e_1_2_1_33_1","unstructured":"Sitharam M. and Zhou Y. 2004. A tractable approximate combinatorial 3d rigidity characterization. 5th Automated Deduction in Geometry (ADG).]]  Sitharam M. and Zhou Y. 2004. A tractable approximate combinatorial 3d rigidity characterization. 5th Automated Deduction in Geometry (ADG).]]"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Sitharam M. 2006. Characterizing well-formed systems on incidences for resolving collections of rigid bodies. UCGA Geometric Constraints. To appear. www.cise.ufl.edu\/~sitharam\/overlap-new.pdf.]]  Sitharam M. 2006. Characterizing well-formed systems on incidences for resolving collections of rigid bodies. UCGA Geometric Constraints. To appear. www.cise.ufl.edu\/~sitharam\/overlap-new.pdf.]]","DOI":"10.1142\/S0218195906002208"},{"volume-title":"Handbook of Discrete and Computational Geometry","author":"Whiteley W.","key":"e_1_2_1_35_1","unstructured":"Whiteley , W. 1997. Rigidity and scene analysis . In Handbook of Discrete and Computational Geometry . CRC Press , 893 --916.]] Whiteley, W. 1997. Rigidity and scene analysis. In Handbook of Discrete and Computational Geometry. CRC Press, 893 --916.]]"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1138450.1138452","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1138450.1138452","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:06:27Z","timestamp":1750259187000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1138450.1138452"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,4]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2006,4]]}},"alternative-id":["10.1145\/1138450.1138452"],"URL":"https:\/\/doi.org\/10.1145\/1138450.1138452","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"type":"print","value":"0730-0301"},{"type":"electronic","value":"1557-7368"}],"subject":[],"published":{"date-parts":[[2006,4]]},"assertion":[{"value":"2006-04-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}