|
= Introduction<ref>Sitharam, M., John, A. S., & Sidman, J. (2018). Handbook of Geometric Constraint Systems Principles. Chapman and Hall/CRC</ref><ref>Bouma, W., Fudos, I., Hoffmann, C., Cai, J., & Paige, R. (1995). Geometric constraint solver. Computer-Aided Design, 27(6), 487-501.</ref> =
The goal of the geometric constraint solver is to find one or more solutions of GCS. The solver also should be able to report if there is no solution. The solver can be tolerated to report no solution but actually there is at least one solution ([https://en.wikipedia.org/wiki/False_positives_and_false_negatives#False_negative_error false negative]). However, it is not allowed to provide a solution that does not exist ([https://en.wikipedia.org/wiki/False_positives_and_false_negatives#False_positive_error false positive]).
#REDIRECT [[Geometric constraint solving]]
Given a [[Geometric Constraint System|geometric constraint system]] (GCS) with <math>n</math> equality constraints, we seek approaches for finding solutions (realizations) or structural characterization of GCS based on the properties of the resulting set of geometrically constrained configurations or realizations. A realization of GCS is the set of zero(es) of the corresponding algebraic system. The [[Geometric Constraint System#Definitions|genericity of a GCS]] is important to know before finding the solutions. Whether a system is [[Geometric Constraint System#Definitions|generic]] determines which type of solvers we can use. It is called generic when each of the variables in a system has approximate [https://en.wikipedia.org/wiki/Degrees_of_freedom_(mechanics) degree-of-freedom] and each [https://en.wikipedia.org/wiki/Constraint_(mathematics) constraint] corresponds to at least one equation.<ref>Sitharam, M., & Zhou, Y. (2004). Mixing features and variational constraints in 3d. CAD, available upon request.</ref> The property of a generic system is well-behaved that we can use both [[#Combinatorial Approaches|combinatorial]] and [[#Algebraic & Automated Geometry Theorem Proving Methods|algebraic algorithm]] to solve it. However, in some special cases, the assignments of variables such as length and angle in equations mapped to the same underlying graph may give different classifications. We categorize a system as [[Geometric Constraint System#Definitions|non-generic]] if it has these nonideal properties. Only [[#Algebraic & Automated Geometry Theorem Proving Methods|algebraic methods]] are able to solve non-generic systems since they are not structural (combinatorial).
{{Redirect category shell|
{{R from draft}}
Given a graph <math>G</math> with constraints <math>C</math>, we can ask GCS problems as follow and solve them separately:
}}
<!-- Template:Draftshell-->
''' Does GCS have at least one real realization and is it a generic or non-generic system?'''
'''- No, it does not have a solution ([[Geometric Constraint System#Definitions|over-constrained]]).'''
<br>Generic system → How to remove dependent constraints edges to make an over-constrained graph well-constrained?<ref>Hoffmann, C., Sitharam, M., & Yuan, B. (2004). Making constraint solvers useable: overconstraints. Comp. Aided Design.</ref> (See [[Geometric Rigidity: Theorems|rigidity method]])
<br>Non-generic system → How to remove dependent equations to make all equations in the system independent?
'''- Yes, it has a finite number set of solutions ([[Geometric Constraint System#Definitions|well-constrained]]).'''
<br>Generic system → Use [[#Combinatorial Approaches|combinatorial approaches]] to solve the realizations (algebraic-based methods also worked but lack of efficiency).
<br>Non-generic system → Use [[#Algebraic & Automated Geometry Theorem Proving Methods|algebraic algorithm]] to solve the realizations.
'''- Yes, it has an infinite number set of solutions ([[Geometric Constraint System#Definitions|under-constrained]]).'''
<br>Generic system → Add more constraint edges to make the graph rigid.
<br>Non-generic system → Use [https://en.wikipedia.org/wiki/Configuration_space_(mathematics) configuration space]<ref>Sitharam, M., & Gao, H. (2010). Characterizing graphs with convex and connected cayley configuration spaces. Discrete & Computational Geometry, 43(3), 594-625.</ref> to describe the solution space.
The geometric constraint solvers can be classified into three categories: 1) [[#Algebraic & Automated Geometry Theorem Proving Methods|algebraic & automated geometry theorem proving methods]]; 2) [[#Combinatorial-Algebraic Algorithm|combinatorial-algebraic algorithm]] and 3) [[#Combinatorial Approaches|combinatorial algorithm]]. The algebraic-based solvers treat GCS as a [https://en.wikipedia.org/wiki/System_of_polynomial_equations system of polynomial equations] and solve it algebraically in either synthetic or algebraic form. The combinatorial algorithm leverages geometric properties of structure such as [[Geometric_Rigidity:_Theorems|rigidity theorems]] to find the realization. At last, the combinatorial-algebraic methods are the hybrid of the former two types of methods.
= Algebraic & Automated Geometry Theorem Proving Methods<ref>Chou, S. C., Gao, X. S., & Zhang, J. Z. (1996). Automated generation of readable proofs with geometric invariants. Journal of Automated Reasoning, 17(3), 325-347.</ref> =
<!-- Instructor: Combine Algebraic with Automated Geometry Theorem Proving Methods -->
Solving a geometric constraint problem is equivalent to [[Automated Geometry Theorem Proving|automated geometry theorem proving]]. Mathematicians have started using computers proving math theory in the mid-20 century. Even though the capacity and computing power is limited at the beginning, computer-assisted proving technique has verified many mathematical theorems never proved by the human in history. [https://en.wikipedia.org/wiki/Proof_by_exhaustion Proof by exhaustion] is the principle of automated geometry theorem proving. Given a mathematical theorem, the computer tests if the theorem hold for all the possible cases. Automated geometry theorem proving demonstrates its versatile ability being used in different fields such as [https://en.wikipedia.org/wiki/Mathematics_education mathematic education] [https://en.wikipedia.org/wiki/Computer-aided_design CAD], [https://en.wikipedia.org/wiki/Robotics robotic], [https://en.wikipedia.org/wiki/Computer_vision computer vision], and [https://en.wikipedia.org/wiki/Artificial_intelligence artificial intelligence].
[[Automated Geometry Theorem Proving|automated geometry theorem proving]] can be classified into three types based on the different foundations: algebraic, synthetic, semi-synthetic, and numerical.
== Synthetic Form ==
[[Automated Geometry Theorem Proving#Synthetic Methods|synthetic method]] does not use coordinates and algebraic formula for representing geometric statements. Instead, it proves theorems by leveraging geometric properties e.g. [https://en.wikipedia.org/wiki/Triangle_inequality triangle inequality] and [https://en.wikipedia.org/wiki/Pythagorean_theorem Pythagoras theorem]. Therefore, the synthetic method is able to produce human-readable proof. The synthetic method is also called the axiom method since it usually adds auxiliary elements when considering the configuration. Sometimes the tremendous number of auxiliary elements can cause a [https://en.wikipedia.org/wiki/Combinatorial_explosion combinatorial explosion] in search space. Thus, developing a proper hierarchy of construction to reduce the unnecessary step is a challenging problem in the synthetic method. Note that geometric properties can be represented as bunches of math equations, so it is practicable to convert synthetic methods into algebraic methods.
There are many automated theorem-proving programs using [[synthetic method]]; for example, Geometry Machine<ref>Gelernter, H., Hansen, J. R., & Loveland, D. W. (1960, May). Empirical explorations of the geometry theorem machine. In Papers presented at the May 3-5, 1960, western joint IRE-AIEE-ACM computer conference (pp. 143-149).</ref> is one of the first automated reasoning systems. After that, the researchers proposed GRAMY<ref>Matsuda, N., & Vanlehn, K. (2004). Gramy: A geometry theorem prover capable of construction. Journal of Automated Reasoning, 32(1), 3-33.</ref> and iGeoTutor<ref>Wang, K., & Su, Z. (2015, June). Automated geometry theorem proving for human-readable proofs. In Twenty-Fourth International Joint Conference on Artificial Intelligence.</ref> based on the deductive database method. Moreover, the logic-based methods are also developed to prove the geometrics theorems such as ArgoCLP<ref>Stojanović, S., Pavlović, V., & Janičić, P. (2010, July). A coherent logic based geometry theorem prover capable of producing formal and readable proofs. In International Workshop on Automated Deduction in Geometry (pp. 201-220). Springer, Berlin, Heidelberg.</ref> and OTTER<ref>Beeson, M., & Wos, L. (2014, July). OTTER proofs in Tarskian geometry. In International Joint Conference on Automated Reasoning (pp. 495-510). Springer, Cham.</ref>
<!--
[[File:Gelernter proof|thumb|Parallelogram of EFGH proved by Gelernter's Geometry Machine]]|Parallelogram of EFGH proved by Gelernter's Geometry Machine
-->
== Semi-synthetic Form ==
The [[Automated Geometry Theorem Proving|semi-synthetic method]] combines synthetic and algebraic methods to obtain the merits of human-readability and computational efficiency. The semi-synthetic method does not use algebra to express geometry problems directly. Instead, it uses geometric quantities to represent conjectures. Then, prove the conjectures by manipulating the equalities in their geometric quantities. As a result, sometimes people also call the semi-synthetic method as coordinate-free methods. Similar to the pure synthetic method, semi-synthetic can also face combinatorial explosion but in most of cases it can produce readable proofs. This approach can be categorized into four types based on the geometric properties they used: area, full-angle, vector, and mass-point methods.
=== Area Methods ===
The area method uses geometric quantities to prove many more complex theorems such as [https://en.wikipedia.org/wiki/Varignon%27s_theorem Varignon’s theorem] and [https://en.wikipedia.org/wiki/Pascal%27s_theorem Pascal's theorem].
<!--
The geometric quantities used in this method are all area-based. The mathematics also extend the research of the area method to solid Euclidean[] and non-Euclidean geometries[] combining with Collins algorithm[] for solving a geometric inequality system[].
such as one property of [[sign area]], if <math> S_{ABC} </math> is sign area of triangle <math> ABC </math> and given an arbitrary point <math>D</math>, <math>S_{ABC} = S_{ABD} + S_{ADC} + S_{DBC}</math>; [[Pythagorean theorem]], the square area of the hypotenuse equals to the sum of the square area of other two edges.
-->
=== Full-angle Methods ===
The principle of the full-angle method is analogy to the area method. The only difference is the geometric quantities it used are angle-based. The full-angle method can prove plenty of non-trivial theorems such as [https://en.wikipedia.org/wiki/Simson_line Simson’s theorem], [https://en.wikipedia.org/wiki/Miquel%27s_theorem Miquel's theorem], and [https://en.wikipedia.org/wiki/Five_circles_theorem Five circle theorem].
<!--
Such as [[inscribed angle theorem]], inscribed angles subtended by the same arc are equal; one property of [[transversal geometric]], if <math>\overline{PX}</math> is parallel to <math>\overline{UV}</math> , then <math>\angle[AB, PX] = \angle[AB, UV]</math>.
-->
=== Vector-based Methods <ref>Chou, S. C., Gao, X. S., & Zhang, J. Z. (1993, August). Automated geometry theorem proving by vector calculation. In Proceedings of the 1993 international symposium on Symbolic and algebraic computation (pp. 284-291).</ref> ===
As the name implies, vector-based method use geometry quantities related to vectors for the proof such as the linearity property of the [https://en.wikipedia.org/wiki/Inner_product_space inner product]. Some more complex theorem such as the [https://en.wikipedia.org/wiki/Altitude_(triangle)#Orthocenter Orthocenter theorem] and [https://en.wikipedia.org/wiki/Cantor%27s_theorem Cantor's Theorem] can be proved by vector-based methods.
<!--
, <math>\langle \alpha A + \beta B, C\rangle = \alpha \langle A, C\rangle + \beta \langle B, C \rangle</math>, and conjugate symmetry property, <math>\langle A, B \rangle = -\langle B,A \rangle</math>.
-->
=== Mass-Point Methods ===
The mass-point method directly utilizes geometric points instead of geometric quantities. The properties of the [https://en.wikipedia.org/wiki/Barycentric_coordinate_system barycentric point] are used as the proposition for the proofs. Many geometric statements can be proved by mass-point methods including [https://en.wikipedia.org/wiki/Pappus%27s_centroid_theorem Pappus' theorem] and
[https://en.wikipedia.org/wiki/Butterfly_theorem Butterfly Theorem] for quadrilaterals.
<!--
Some examples of barycentric point properties: 1) <math> xAB = yPQ \;\; iff \;\; xA - xB = yP - yQ</math>; 2) Any point <math>P</math> on plane <math>ABC</math> can be expressed as the linear combination of <math>A</math>, <math>B</math>, <math>C</math> uniquely in the form <math>P = aA + bB + (1-a-b)C</math>.
-->
== Algebraic Form ==
The [[Automated Geometry Theorem Proving#Algebraic Methods|algebraic method]] translates the representation of geometric statements into a [https://en.wikipedia.org/wiki/Nonlinear_system system of nonlinear equations]. The solutions can be obtained by solving a system of equations with nonlinear equation solvers. The algebraic method has the advantages of generality, dimension independent, and all synthetics methods also can be translated into algebraic form. However, the major drawback is that it is unable to generate human-readable proofs. Moreover, some procedures in the proofs do not have any geometric synthetic meaning.
=== Numerical Methods ===
The [https://en.wikipedia.org/wiki/Numerical_analysis numerical method] translates geometric constraints into algebraic linear or non-linear equations. Then using numerical methods such as [https://en.wikipedia.org/wiki/Newton%27s_method Newton-Raphson], [https://en.wikipedia.org/wiki/Lagrange_polynomial Lagrange interpolation polynomial], and [https://en.wikipedia.org/wiki/Gaussian_elimination Gaussian elimination] to approach the solution.
=== Symbolic Methods ===
The symbolic methods such as [https://en.wikipedia.org/wiki/Buchberger%27s_algorithm Buchberger] and [[Automated Geometry Theorem Proving#Algebraic Methods|Wu-Ritt]] are able to compute the [https://en.wikipedia.org/wiki/Gr%C3%B6bner_basis Gröbner basis] with a given system of equations. These methods map the system of polynomial equations to a triangular system, this procedure also called [https://en.wikipedia.org/wiki/Triangular_matrix#Triangularisability triangularization]. The solution of the triangular system is equivalent to the given system and can be solved in exponential running time. On the other hand, the author Kondo utilizes [https://en.wikipedia.org/wiki/Buchberger%27s_algorithm Buchberger's Algorithm] to formulate polynomial equations that can record the addition and deletion of constraints.
<!--Instructor: This should go under Algebraic Methods-->
=== Coordinate-Free Method ===
The coordinate-free methods are the solvers for [https://en.wikipedia.org/wiki/Incidence_geometry incidence geometry]. The geometry theorems are called incidence geometry which solves the incident properties between geometric elements such as line circle intersects problems. The feature of incidence geometry is pure qualitative without measurement. Bracket algebra<ref>Sidman, J. & Traves, W. Cayley Factorizationandspecial Positions. In: Sitharaman, M., St.John, A., and Sidman, J. (ed.), Handbook of Geometric Constraints Systems: Principles.</ref> and [https://en.wikipedia.org/wiki/Grassmann%E2%80%93Cayley_algebra Grassmann-Cayley algebra] are the standard treatments in coordinate-free methods for dealing with incidence statements and constructions.
= Combinatorial-Algebraic Algorithm =
Combinatorial-algebraic algorithms aim at solving graph-based problems. In graph-based problem, given a [https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)#Undirected_graph undirected graph] <math> G = (V, E) </math> sitting on top of a framework, where the nodes <math>V</math> represent the geometric elements and the edges denote the constraints. When the numbers of geometric elements <math>|V|</math> and constraints <math>|E|</math> are low, it is possible to directly translate the graph into algebraic form with a system of polynomial equations. However, with a more complex graph, the growth of the number of geometric elements and constraints makes the pure algebraic methods no longer practical. The combinatorial-algebraic algorithm breaks the system into several subsystems and solves them separately, then combine the solutions from each subsystem into the solution for the entire system. The solving time for the combinatorial-algebraic algorithm is much faster than the pure algebraic method when solving complex graph-based problems. This is because the solving time increases exponentially along with the number of variables. And combinatorial-algebraic algorithms only need to solve subsystems with much fewer variables than the whole system.
The combinatorial-algebraic algorithm can be classified into [[Decomposition Recombination Planning|decomposition recombination planning (DR-planning)]] and [[#Propagation Method|propagation method]].
== Decomposition Recombination Planning ==
The [[Decomposition Recombination Planning|decomposition recombination planning (DR-planning)]] method designs a plan for decomposing a constraint system into multiple smaller subsystems then [[Recombination of Geometric Constraint Systems|recombining solutions]] of these subsystems. DR-planning is efficient but can not be applied to any arbitrary graph-based problems e.g. non-generic system. The solutions of small subsystems must be able to recombine into a global solution of the entire system. Specifically, it is required to substitute the solutions of subsystems to the larger problems and eliminate its variables. By hierarchically substituting solutions of smaller subsystems to larger ones, the entire system can be easy to solve in the end<ref>Baker, T., Sitharam, M., Wang, M., & Willoughby, J. (2015). Optimal decomposition and recombination of isostatic geometric constraint systems for designing layered materials. Computer Aided Geometric Design, 40, 1-25.</ref><ref>Sitharam, M., & Zhou, Y. (2004). Solving minimal, wellconstrained, 3D geometric constraint systems: combinatorial optimization of algebraic complexity.</ref><ref>Hoffmann, C. M., Lomonosov, A., & Sitharam, M. (2001). Decomposition of Geometric Constraints Part I: performance measures & Part II: new algorithms. J. of Symbolic Computation, 31(4).</ref><ref>Hoffman, C. M., Lomonosov, A., & Sitharam, M. (2001). Decomposition plans for geometric constraint problems, part II: new algorithms. Journal of Symbolic Computation, 31(4), 409-427.</ref><ref>Hoffmann, C. M., Lomonosov, A., & Sitharam, M. (1999, September). Planning Geometric constraint decomposition via optimal graph transformations. In International Workshop on Applications of Graph Transformations with Industrial Relevance (pp. 309-324). Springer, Berlin, Heidelberg.</ref>.
=== Decomposition ===
==== Ruler and Compass ====
[[Decomposition Recombination Planning#Types of Decomopsition|Ruler and compass]] is a constructive method leveraging the fact that the most complex configuration in engineering drawings can be solved by using small tools like a ruler and compass. This method only considers the graph comprises of points, lines, circles and arcs of a circle. The ruler and compass method has an analyzer and a constructor. The analyzer determines whether the given constraint-graph is solvable by generating a sequence of constructive steps to test if the constraints hold. The constructor in charge of numerical computation, which uses the construction steps to produce geometric elements for the current dimension values.
==== Triangle (Tree) Decomposition ====
[[Tree/ Triangle Decomposable Graphs|Triangle decomposition]] method as known as tree decomposition works on a graph built from constraint equations. The tree decomposition methods can be categorized as a top-down and bottom-up approach. The top-down method views GCS as several independently solvable subsystems. After the solutions for each subsystem have been solved, those solutions can be combined into new constrains for solving the remaining unsolved GCS at a higher level. Similarly, the decomposition can also be done by bottom-up, where the triples of solved geometric objects seek pairwise that shares a geometric primitive.
Owen's graph analysis<ref>Owen, J. C. (1991, May). Algebraic solution for geometry from dimensional constraints. In Proceedings of the first ACM symposium on Solid modeling foundations and CAD/CAM applications (pp. 397-407).</ref> is the pioneer of the top-down method which decomposes the constraint graph into smaller [https://en.wikipedia.org/wiki/SPQR_tree tri-connected components]. Then, recursively split the graph into three subgraphs by cutting at articulation vertices. The triangles in each subgraph correspond to the system of quadratic equations that easy to be solved. Bouma's method is the first bottom-up decomposition approach. It first finds the triangles with solvable subsystems in the graph then combines the solutions the same with the top-down approach. The bottom-up approach has the advantage of detecting over-constrained subgraphs.
==== Maximum Matching-based Decomposition ====
Similar to the algorithms for detecting [[Geometric Rigidity: Theorems|rigidity of framework]]. This type of DR-planning algorithm performs [[Decomposition Recombination Planning#Types of Decomopsition|maximum matching]] on [https://en.wikipedia.org/wiki/Bipartite_graph bipartite graphs] to generate the DR-plan. Such algorithms include [https://en.wikipedia.org/wiki/Dulmage%E2%80%93Mendelsohn_decomposition Dulmage-Mendelsohn Decomposition] and Assur Decomposition<ref>Assur, L. V., & Artobolevskij, I. I. (1952). Issledovanie ploskih steržnevyh mehanizmov s nizšimi parami s točki zreniâ ih struktury i klassifikacii. Izdatel'stvo Akademii Nauk SSSR.</ref>.
==== Network Flow-based Decomposition ====
The bottom-up DR-planning methods use network flow techniques to solve the GCS problems.<ref>Hoffmann, C. M., Lomonosov, A., & Sitharam, M. (1998). Geometric constraint decomposition. In Geometric constraint solving and applications (pp. 170-195). Springer, Berlin, Heidelberg.</ref> The bottom-up method guarantees that the output of the DR-plan has cluster minimality where no sibset of children union is dense. The approaches in this category including [[Decomposition Recombination Planning#Types of Decomopsition|frontier vertex decomposition]]<ref>Oung, J., Sitharam, M., Moro, B., & Arbree, A. (2001, May). FRONTIER: fully enabling geometric constraints for feature-based modeling and assembly. In Proceedings of the sixth ACM symposium on Solid modeling and applications (pp. 307-308).</ref> and [[Decomposition Recombination Planning#Types of Decomopsition|canonical decomposition]].
=== Optimization of Recombination ===
After decomposition and obtained the realization for each subsystem, we need to recombine all solutions of each subsystem to get the final solution for the entire system. The algorithm leverages incidence tree parametrizations for a collection of rigid bodies is proposed to minimize the algebraic complexity of the [[Recombination of Geometric Constraint Systems|recombination]] process<ref>Sitharam, M., Zhou, Y., & Peters, J. (2010). Reconciling conflicting combinatorial preprocessors for geometric constraint systems. International Journal of Computational Geometry & Applications, 20(06), 631-651.</ref><ref>Sitharam, M., Peters, J., & Zhou, Y. (2004). Solving minimal, wellconstrained, 3d geometric constraint systems: combinatorial optimization of algebraic complexity. Automated deduction in Geometry (ADG).</ref><ref>Sitharam, M. (2006). Well-formed systems of point incidences for resolving collections of rigid bodies. International Journal of Computational Geometry & Applications, 16(05n06), 591-615.</ref><ref>Sitharam, M., Arbree, A., Zhou, Y., & Kohareswaran, N. (2006). Solution space navigation for geometric constraint systems. ACM Transactions on Graphics (TOG), 25(2), 194-213.</ref><ref>Peters, J., Sitharam, M., Zhou, Y., & Fan, J. (2006). Elimination in generically rigid 3d geometric constraint systems. In Algebraic Geometry and Geometric Modeling (pp. 205-216). Springer, Berlin, Heidelberg.</ref>.
== Propagation Method ==
The propagation method translates the constraints into a system of equations made up of constants and variables. Then an undirected graph can be built by treating the equations, variables, and constants as nodes and the occurrence of variables and constants in equations as edges. Next, the propagation methods aim at transforming the undirected graph into a directed graph that all equations can be solved in turn. The method begins the computation from the node with constants then tries to propagate the known variable, solutions and constants, to the next node to eliminate the unknown variables.
[https://en.wikipedia.org/wiki/Constraint_programming Constraint Programming (CP)]<ref>Leler, W. (1988). Constraint programming languages: their specification and generation. Addison-Wesley Longman Publishing Co., Inc..</ref> is a standard tool of the propagation method. The numerical CP techniques such as ThingLab<ref>Borning, A. (1981). The programming language aspects of ThingLab, a constraint-oriented simulation laboratory. ACM Transactions on Programming Languages and Systems (TOPLAS), 3(4), 353-387.</ref>, Sketchpad<ref>Sutherland, I. E. (1964). Sketchpad a man-machine graphical communication system. Simulation, 2(5), R-3.</ref>, [https://en.wikipedia.org/wiki/TK_Solver TK! Solver] and Juno<ref>Nelson, G. (1985, July). Juno, a constraint-based graphics system. In Proceedings of the 12th annual conference on Computer graphics and interactive techniques (pp. 235-243).</ref> iteratively
approximate the solutions for constraint programs containing cycles. On the other hand, the symbolic methods e.g. Steele's Constraint Language<ref>Steele Jr, G. L. (1980). The definition and implementation of a computer programming language based on constraints.</ref>, Magritte<ref>Gosling, J. A. (1984). Algebraic constraints.</ref>, and IDEAL<ref>Van Wyk, C. J. (1981). A LANGUAGE FOR TYPESETTING GRAPHICS.</ref> are based on algebraic simplification technique. Note that none of the propagation techniques can guarantee to find the solution if there is one. The propagation method is vulnerable for dealing with circularly constrained problems.
= Combinatorial Approaches<ref>Sitharam, M. (2005). Combinatorial approaches to geometric constraint solving: Problems, progress, and directions. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 67, 117.</ref><ref>Wang, M., & Sitharam, M. (2014, July). Combinatorial rigidity and independence of generalized pinned subspace-incidence constraint systems. In International Workshop on Automated Deduction in Geometry (pp. 166-180). Springer, Cham.</ref> =
Unlike algebraic methods, combinatorial approaches only deal with abstract objects and constraints. These methods determine the properties of the given framework <math> (G, p)</math> including the analysis of the constraint graphs and [[#Constraint Graph & Degree of Freedom|degree of freedom (DOF)]]; moreover, categorizing the [[Geometric Rigidity: Types of Frameworks|types of frameworks]] and determining the [[Structural (Combinatorial) Rigidity|rigidity of structures]]. It is limited to apply combinatorial solvers only on generic GCS since all the theorems and algorithms are using the corresponding graph of the system.
== Constraint Graph & Degree of Freedom ==
Let a geometric constraint graph <math>G = (V, E, w)</math> corresponding to a GCS with weighting <math>w(v)</math> and <math>w(e)</math> for vertices and edges. These weighting represent the number of DOF available to a <math>V</math> with its corresponding object removed by the incident edges. Given a subgraph <math>A \subseteq G</math>, we can compute its dense <math>d(A) = \sum\nolimits_{e\in A}w(e) - \sum\nolimits_{v \in A}w(v)</math>. The dense <math>D</math> can be used to determine the constrainedness and degree of freedom of graph.
== Types of Framework ==
Assigning different CGS with a suitable [[Geometric Rigidity: Types of Frameworks|type of framework]] and solve it is also an important topic in combinatorial approaches. There are various kinds of structure such as [[Geometric Rigidity: Types of Frameworks#Frameworks|bar-joint]], [[Geometric Rigidity: Types of Frameworks#Frameworks|Body-and-Cad]]<ref>Haller, K., John, A. L. S., Sitharam, M., Streinu, I., & White, N. (2012). Body-and-cad geometric constraint systems. Computational Geometry, 45(8), 385-405.</ref>, and [[Geometric Rigidity: Types of Frameworks#Frameworks|Body bar hinge]].
== Structural Rigidity ==
The algorithms for [[Structural (Combinatorial) Rigidity|structural regidity]] are able to determine the flexibility of the structure formed by rigid bodies and flexible linkages. There are many classic algorithms:
The [https://en.wikipedia.org/wiki/Matroid matroid] is used to record the rigidity of rod-and-hinge linkages in any dimensional space. And in two-dimensional space, the classic algorithm [[Laman's Theorem|Laman graphs]] provides a rule to track the internal degree of freedom (DOF) of the system by counting the numbers of edges and vertices.
Some other approaches are proposed to test the bar-joint rigidity for structure in two-dimensional space. For example, network flow-based algorithm<ref>Imai, H. (1985). On combinatorial structures of line drawings of polyhedra. Discrete Applied Mathematics, 10(1), 79-92.</ref>, matroid sums<ref>Gabow, H. N., & Westermann, H. H. (1992). Forests, frames, and games: algorithms for matroid sums and applications. Algorithmica, 7(1-6), 465.</ref>, bipartite matching algorithm<ref>Hendrickson, B. (1992). Conditions for unique graph realizations. SIAM journal on computing, 21(1), 65-84.</ref>, and [[Pebble Game|pebble game]].
Extend to 3-dimensional space, [https://en.wikipedia.org/wiki/Cauchy%27s_theorem_(geometry) Cauchy’s theorem] shows that in all [https://en.wikipedia.org/wiki/Convex_polygon convex polyhedrons] are rigid and also globally rigid. And Raoul Bricard and Robert Connelly show that flexible polyhedra which are non-convex polyhedron is not rigid.
<!---
'''Geometric constraint solving''' is [[constraint satisfaction]] in a [[computational geometry]] setting, which has primary applications in [[computer aided design]].<ref>{{cite book|last1=Roller|first1=edited by Beat Brüderlin, Dieter|title=Geometric Constraint Solving and Applications|date=1998|publisher=Springer Berlin Heidelberg|___location=Berlin, Heidelberg|isbn=978-3-642-58898-3|pages=3-23|url=https://www.springer.com/gp/book/9783642637810|language=en}}</ref> A problem to be solved consists of a given set of geometric elements and a description of geometric [[Constraint (computer-aided design)|constraints]] between the elements, which could be non-parametric (tangency, horizontality, coaxiality, etc) or parametric (like distance, angle, radius). The goal is to find the positions of geometric elements in 2D or 3D space that satisfy the given constraints,<ref>{{cite book|last1=Christoph M. Hoffmann|last2=Pamela J. Vermeer|title=Geometric constraint solving in R2 and R3|url=https://pdfs.semanticscholar.org/5495/673d9bda0ec575a2185ddb890f887328be58.pdf}}</ref> which is done by dedicated software components called geometric constraint solvers.
Geometric constraint solving became an integral part of CAD systems in the 80s, when Pro/Engineer firstly introduced a novel concept of feature-based parametric modeling concept.<ref>{{cite book|last1=Robert Joan-Arinyo|title=Basics on Geometric Constraint Solving|url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.331.9554&rep=rep1&type=pdf}}</ref><ref>{{cite book|last1=R. Anderl|last2=R. Mendgen|title=Modelling with constraints: theoretical foundation and application|url=http://www.sciencedirect.com/science/article/pii/0010448595000232}}</ref>
There are additional problems of geometric constraint solving that are related to sets of geometric elements and constraints: dynamic moving of given elements keeping all constraints satisfied,<ref>{{cite book|title=A constraint-based dynamic geometry system|last1=Marc Freixas|last2=Robert Joan-Arinyo|last3=Antoni Soto-Riera|url=http://www.sciencedirect.com/science/article/pii/S0010448509000876}}</ref> detection of over- and under-constrained sets and subsets,<ref>{{cite book|last1=Rossignac|first1=Jaroslaw|last2=SIGGRAPH|first2=Joshua Turner, editors ; sponsored by ACM|title=Proceedings : Symposium on Solid Modeling Foundations and CAD/CAM Applications, Radisson Plaza Hotel, Austin, Texas, June 5-7, 1991|date=1991|publisher=Association for Computing Machinery|___location=New York|isbn=0-89791-427-9}}</ref><ref>{{cite book|title=Extensions of the witness method to characterize under-, over- and well-constrained geometric constraint systems|url=http://www.sciencedirect.com/science/article/pii/S0010448511001606|last1=Simon E.B.Thierry|last2=Pascal Schreck|last3=Dominique Michelucci|last4=Christoph Fünfzig|last5=Jean-David Génevaux}}</ref> auto-constraining of under-constrained problems, etc.
== Methods ==
A general scheme of geometric constraint solving consists of modeling a set of geometric elements and constraints by a system of equations, and then solving this system by non-linear algebraic solver. For the sake of performance, a number of [[Decomposition method (constraint satisfaction)|decomposition techniques]] could be used in order to decrease the size of an equation set:<ref>{{cite book|title=A formalization of geometric constraint systems and their decomposition|last1=Pascal Mathis|last2=Simon E. B. Thierry|url=https://link.springer.com/article/10.1007%2Fs00165-009-0117-8}}</ref> decomposition-recombination planning algorithms,<ref>{{cite book|title=Decomposition Plans for Geometric Constraint Systems, Part I: Performance Measures for CAD|url=http://www.sciencedirect.com/science/article/pii/S0747717100904024|last1=Christoph M.Hoffman|last2=Andrew Lomonosov|last3=Meera Sitharam}}</ref><ref>{{cite book|title=Decomposition Plans for Geometric Constraint Problems, Part II: New Algorithms|url=http://www.sciencedirect.com/science/article/pii/S0747717100904036|last1=Christoph M.Hoffman|last2=Andrew Lomonosov|last3=Meera Sitharam}}</ref> tree decomposition,<ref>{{cite book|title=h-graphs: A new representation for tree decompositions of graphs|url=http://www.sciencedirect.com/science/article/pii/S0010448515000688|last1=Marta Hidalgoa|last2=Robert Joan-Arinyo}}</ref> C-tree decomposition,<ref>{{cite book|title=A C-tree decomposition algorithm for 2D and 3D geometric constraint solving|url=http://www.sciencedirect.com/science/article/pii/S0010448505000813|last1=Xiao-Shan Gao|last2=Qiang Lin|last3=Gui-Fang Zhang}}</ref> graph reduction,<ref>{{cite book|title=A 2D geometric constraint solver using a graph reduction method|url=http://www.sciencedirect.com/science/article/pii/S0965997810001006|last1=Samy Ait-Aoudia|last2=Sebti Foufou}}</ref> re-parametrization and reduction,<ref>{{cite book|title=Re-parameterization reduces irreducible geometric constraint systems|url=http://www.sciencedirect.com/science/article/pii/S0010448515001116|last1=Hichem Barki|last2=Lincong Fang|last3=Dominique Michelucci|last4=Sebti Foufou}}</ref> computing fundamental circuits,<ref>{{cite book|title=Decomposition of geometric constraint graphs based on computing fundamental circuits. Correctness and complexity|url=http://www.sciencedirect.com/science/article/pii/S001044851400030X|last1=R.Joan-Arinyo|last2=M.Tarrés-Puertas|last3=S.Vila-Marta}}</ref> body-and-cad structure,<ref>{{cite book|title=Body-and-cad geometric constraint systems|url=http://www.sciencedirect.com/science/article/pii/S0925772112000235|last1=Kirk Haller|last2=Audrey Lee-St.John|last3=Meera Sitharam|last4=Ileana Streinu|last5=Neil White}}</ref> or the witness configuration method.<ref>{{cite book|title=Geometric constraint solving: The witness configuration method|url=http://www.sciencedirect.com/science/article/pii/S001044850600025X|last1=Dominique Michelucci|last2=Sebti Foufou}}</ref>
Some other methods and approaches include the degrees of freedom analysis,<ref>{{cite book|last1=Kramer|first1=Glenn A.|title=Solving geometric constraint systems : a case study in kinematics|date=1992|publisher=MIT Press|___location=Cambridge, Mass.|isbn=9780262111645|edition=1:a upplagan.|url=https://mitpress.mit.edu/books/solving-geometric-constraint-systems}}</ref><ref>{{cite book|title=A geometric constraint solver for 3-D assembly modeling|url=https://link.springer.com/article/10.1007%2Fs00170-004-2391-1?LI=true|last1=Xiaobo Peng|last2=Kunwoo Lee|last3=Liping Chen}}</ref> symbolic computations,<ref>{{cite book|title=Solving Geometric Constraint Systems II. A Symbolic Approach and Decision of Rc-constructibility|last1=Xiao-Shan Gao|last2=Shang-Ching Chou|url=https://pdfs.semanticscholar.org/a1c3/6b6aa83ecc85d28a7cdde258ab1355613926.pdf}}</ref> rule-based computations,<ref name="purdue">{{cite book|title=A Geometric Constraint Solver|date=1993|url=http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=2067&context=cstech|last1=William Bouma|last2=Ioannis Fudos|last3=Christoph M. Hoffmann|last4=Jiazhen Cai|last5=Robert Paige}}</ref> constraint programming and constraint propagation,<ref name="purdue" /><ref>{{cite book|title=Stabilizing 3D modeling with geometric constraints propagation|url=http://www.sciencedirect.com/science/article/pii/S1077314209001003|last1=Michela Farenzena|last2=Andrea Fusiello}}</ref> and genetic algorithms.<ref>{{cite book|title=Constructive Geometric Constraint Solving: A New Application of Genetic Algorithms|url=https://link.springer.com/chapter/10.1007/3-540-45712-7_73|last1=R. Joan-Arinyo|last2=M.V. Luzón|last3=A. Soto}}</ref>
Non-linear equation systems are mostly solved by iterative methods that resolve the linear problem at each iteration, the Newton-Raphson method being the most popular example.<ref name="purdue" />
== Applications ==
Geometric constraint solving has applications in a wide variety of fields, such as computer aided design, mechanical engineering, [[inverse kinematics]] and [[robotics]],<ref>{{cite web|title=Geometric constraint solver|url=http://www.coppeliarobotics.com/helpFiles/en/geometricConstraintSolverModule.htm}}</ref> architecture and construction, molecular chemistry,<ref>{{cite book|title=Leading a continuation method by geometry for solving geometric constraints|date=2014|last1=Rémi Imbach|last2=Pascal Schreck|last3=Pascal Mathis|url=http://www.sciencedirect.com/science/article/pii/S0010448513001668}}</ref> and geometric theorem proving. The primary application area is computer aided design, where geometric constraint solving is used in both parametric history-based modeling and variational direct modeling.<ref>{{cite book|title=Variational Direct Modeling: How to Keep Design Intent in History-Free CAD|date=2008|url=http://www.ledas.com/pdf/VariationalDirectModeling.pdf|last1=Dmitry Ushakov}}</ref>
== Software implementations ==
The list of geometric constraint solvers includes at least
* DCM (Dimensional Constraint Manager),<ref>{{cite web|title=2D Dimensional Constraint Manager (D-Cubed 2D DCM)|url=https://www.plm.automation.siemens.com/en/products/open/d-cubed/2ddcm/index.shtml}}</ref> a commercial solver from D-Cubed (subsidiary of [[Siemens PLM Software]]), integrated in [[AutoCAD]], [[SolidWorks]], [[PTC Creo|Creo]], and many other popular CAD systems;<ref>{{cite web|title=D-Cubed Customers|url=https://www.plm.automation.siemens.com/en/products/open/d-cubed/customers/}}</ref>
* LGS,<ref>{{cite web|title=Bricsys Component Technology for Constraint Management in 2D/3D|url=https://www.bricsys.com/el-gr/applications/developers/components/}}</ref> a commercial solver developed by LEDAS and currently owned by Bricsys, integrated in [[Cimatron#CimatronE|Cimatron E]] and [[BricsCAD]];<ref>{{cite news|title=Cimatron to Introduce New Motion Simulator Powered by LEDAS LGS 3D|url=http://www.3dcadinfo.com/news/1794/cimatron-to-introduce-new-motion-simulator-powered-by-ledas-lgs-3d/}}</ref><ref>{{cite web|title=Exclusive Q&A: What it means, now that Bricsys bought IP from Ledas|url=http://worldcadaccess.typepad.com/blog/2011/10/exclusive-qa-what-it-means-now-that-bricsys-bought-ip-from-ledas.html}}</ref>
* C3D Solver,<ref>{{cite web|title=C3D Solver|url=http://c3dlabs.com/en/products/solver/}}</ref> a commercially available solver which is a part of [[C3D Toolkit]], integrated into KOMPAS-3D;<ref>{{cite web|title=C3D Toolkit|url=http://c3dlabs.com/en/products/c3d-kernel/}}</ref>
* GeoSolver,<ref>{{cite web|title=GeoSolver Project Page|url=http://geosolver.sourceforge.net/}}</ref> a [[GNU Public License]] [[Python (programming language)|Python]] package for geometric constraint solving.
== References ==
{{Reflist}}
--->
<!--- Categories --->
[[:Category:Constraint programming]]
[[:Category:Articles created via the Article Wizard]]
<!--Instructor 2nd:
Please put one small paragraph in the beginning on the different constraint solving problems. This is repeated in your page and geometric constraint solving page. That's ok.
Given a GCS C with n equality constraints, we seek approaches for finding realizations and/or giving a structural characterization of C based on properties of the resulting set S of geometrically constrained configurations or realizations. Hence, one can ask GCS questions as follows. Given a graph G and constraints C,
Is there a solution(realization) over the reals?
Does it have a finite number of realizations? one realization or many realizations?
Does it have an infinite number of realizations? I.e, is it underconstrained? If so, how to make it well-constrained?
If overconstrained, how to remove dependent constraints?
If infinitely many solutions, how to describe the configuration space?
-->
<!--Instructor 2nd: there is a lot of detail in the automated geometry theorem proving page that you do not need to repeat here.
Just cite it and refer to it.
-->
<!--Instructor 2nd: in general, please look at the wiki projects diagram linked from the course page and make all the links to
student or other wikipedia pages shown there. They have to be linked within the text, not just
"see also."
-->
<!--Instructor 2nd: Solving Generic vs. non-generic systems is a key point and has not been addressed. Algebraic/Synthetic methods
address many nongeneric cases in comparison to combinatorial-algebraic methods, which are primarily for generic systems.
-->
<!--Instructor 2nd: For the combinatorial-algebraic methods, please refer to this survey
https://www.semanticscholar.org/paper/Combinatorial-Approaches-to-Geometric-Constraint-Sitharam/383aa912c715179225cf16ce90bfd7f05a80a277?tab=abstract&citingPapersSort=is-influential&citingPapersLimit=10&citingPapersOffset=0&year%5B0%5D=0&year%5B1%5D=0&citedPapersSort=is-influential&citedPapersLimit=10&citedPapersOffset=0
-->
<!-- Instructor 2nd: I do not see anything about either general deomposition, or recombination part in your
article. You don't need to say much, just the key idea and then link to those pages. Currently it seems as though the entire
combinatorial-algebraic part is just tree decomposability and quadratic solvability. They are actually just the basics.
-->
<!-- Instructor 2nd
Please refer to all the relevant articles from my webpage
(our group has primary expertise in combinatorial-algebraic methods) on
decomposition (combinatorial) and recombination (algebraic).
Troy Baker, Meera Sitharam, Rahul Prabhu Geometric Constraint Decomposition: The General Case In Meera Sitharam, Audrey St John, Jessica Sidman, editors, Handbook of Geometric Constraint Systems Principles, chapter 7, pages 285–310. CRC Press, 2018
Menghan Wang, Meera Sitharam Combinatorial Rigidity and Independence of Generalized Pinned Subspace-Incidence Constraint Systems Proceedings of the ADG 2015
Troy Baker, Meera Sitharam, Menghan Wang, Joel Willoughby Optimal Decomposition and Recombination of Isostatic Geometric Constraint Systems for Designing Layered Materials Computer Aided Geometric Design 2015
Recombination:
M. Sitharam, Y. Zhou, J. Peters Reconciling Combinatorial Preprocessors for Geometric constraint systems International Journal of Computational Geometry and Applications, 20(6):631–651, 2010.
K. Haller, A. Lee, M. Sitharam, I. Streinu, N. White `` Body-and-Cad constraint systems'' ACM-SAC Geometric constraints and Reasoning, 2009 and FwCG 2008. Computational Geometry Theory and Applications. CoRR abs/1006.1126: (2010) To appear
Recombination:
M. Sitharam, J. Peters, Y. Zhou, ``Combinatorial optimization of algebraic complexity of minimal geometric constraint sytems'' Journal of Symbolic Computation, 2010
M. Sitharam, H. Gao Characterizing graphs with convex configuration spaces (arXiv) Discrete and Computational Geometry 2009.
Recombination:
M. Sitharam "Characterizing Well-formed systems of incidences for resolving collections of rigid bodies" IJCGA, Vol. 16, 5-6, 2006
M. Sitharam, J. Oung, A. Arbree and Y. Zhou, "Mixing features and variational constraints in 3D" CAD 2006
Recombination:
M. Sitharam, A. Arbree, Y. Zhou, N. Kohareswaran "Solution management and navigation for 3D geometric constraint systems" ACM TOG 2006
Recombination:
Jorg Peters and JianHua Fan and Meera Sitharam and Yong Zhou, Elimination in generically rigid 3{\sf D} geometric constraint systems, Proceedings of Algebraic Geometry and Geometric Modeling,Nice, 27-29 September 2004, Springer Verlag, 1-16, 2005.
M. Sitharam ``Combinatorial approaches to geometric constraint solving: problems, progress, directions,'' AMS-DIMACS book on computer aided design and manufacturing. Edited by Dutta, Janardhan, Smid. 2005.
M. Sitharam, Y.Zhou, J. Peters "Solving minimally decomposed 3D geometric constraint systems: optimizing algebraic complexity" 5th to Automated Deduction in Geometry, ADG 2004. Talk given at ACA 2004.
C. Hoffman, M. Sitharam, B. Yuan, ``Making constraint solvers useable: overconstraints,'' (pdf file) CAD, 2004.
J-J. Oung, M. Sitharam, B. Moro, A. Arbree, FRONTIER: fully enabling geometric constraints for feature based modeling and assembly (pdf file)
gzipped ps file Proceedings of ACM Solid Modeling symposium, 2001.
C. Hoffman, A. Lomonosov, M. Sitharam, Decomposition of Geometric Constraints Part I: performance measures, (pdf file)
gzipped ps file Journal of Symbolic Computation Vol. 31, No. 4, April 2001
C. Hoffman, A. Lomonosov, M. Sitharam, Decomposition of Geometric Constraints Part II: new algorithms, (pdf file)
C. Hoffman, A. Lomonosov, M. Sitharam, Planning Geometric constraint decompositions via graph transformations (pdf file)
gzipped ps file Proceedings of AGTIVE '99 (Graph Transformations with Industrial Relevance), Springer lecture notes, LNCS 1779, eds Nagl, Schurr, Munch, pp. 309-324, 1999.
C. Hoffman, M. Sitharam, A. Lomonosov, ``Geometric constraint decomposition,'' (pdf file)
gzipped ps file in "Geometric Constraint Solving and Applications", Springer Verlag, Edited by Beat Br\" uderlin and Dieter Roller, 1998.
-->
<!--Instructor: You should sit down with the student writing the Geometric Constraint Systems page, and divide the topics clearly.
You should concentrate on the Geometric Constraint Solving Algorithms, for the various types of
problems on geometric constraint systems.
There are roughly 3 types: Algebraic Algorithms; Automated Geometry Theorem Proving algorithms (which overlap with algebraic algorithms); and Combinatorial Algorithms; and Combinatorial-Algebraic Algorithms. Furthermore, the algebraic algorithms often are semi-numerical.
You can connect to pages that will exist on tree-decomposable systems and Quadratic Solvability(triangle decomposition), decomposition, recombination, pebble game, combinatorial and geometric rigidity.
His should define geometric constraint system, define the geometric constraint graph, connect to frameworks and linkages, define configuration/solution/realization space of a geometric constraint system including the group of trivial motions (connect to Kempe's linkage page), give different examples of types of geometric constraint systems and their trivial motion groups, connect to different types of frameworks in the combinatorial rigidity page, describe the various problems on Geometric Constraint Systems and talk about genericity, connect to related concepts and questions on frameworks and linkages. Connect to the pages on geometric constraint solving, combinatorial rigidity (types of frameworks), Cayley configuration space. -->
<!-- second feedback
It is very well structured and organized and overall, I think it is a quite well-documented article.
I understand this is not the final version.
My critique is about how I think it might be better if some explained below are added.
It is also a problem of mine, but you have a lot of terms that are referring to other wiki pages in your article, however, it seems it needs to be correctly done.
Some of the methods explained in each section might need to have more specific examples.
For example,
1. for methods in the (semi-)synthetic form section, it would be more understandable with specific examples.
2. Ruler and Compass are also the same and it might be easier to give an example.
For some methods(algorithms), if the running time of each one is introduced, it might help readers to get the gist. For example, you introduced two symbolic methods such as Buchberger and Wu-Ritt methods, and such methods can solve general nonlinear systems of algebraic equations but may require exponential running times.
For some methods, under what circumstances(which systems or when) such methods should be used also might be given and it might support the article more.
In addition, you can explain whether or not there is an alternative method in case a method fails.
Furthermore, if some methods are explained in detail, it would be better.
-->
<!-- Many topics under this section are overlapped between two topics (your topic and Geometry Constraint System which is mine). I do not know if it should go as it is but if it is not, we need to talk regarding the distribution or level of details. -->
<!--
The geometric objects in GCS can be distance, incidence, tangency, etc. It seems there is a mistake in this sentence because they are constraints, not geometric objects.
-->
<!--
Geometric Constraint Solving approaches can be broadly divided into 1)algebraic 2)rule-constructive 3)graph-based approaches. Probably such divisions of approaches also can be explained.
-->
<!--
It is hard to say that some parts might need to be more detailed because it is a draft of the document.
Overall, the article in the topic seems well-structured and subsections are sufficient.
-->
| 