Algorithms for Identifying Rigid Subsystems in Geometric Constraint Systems

1 Introduction

Geometric constraint satisfaction problems (GCSPs) arise naturally in several areas, such as CAD, robotics and molec­ ular biology. The rigidity concept is in the heart of many of these problems: deciding whether a GCSP is rigid or not, de­ tecting rigid or over-rigid sub-parts, and so on.

Several methods [Kramer, 1992; Bouma et al., 1995; Dufourd et al., 1998; Lamure and Michelucci, 1998; Hoff­ mann et al., 2000; Jermann et al., 2000; Jermann, 2002] for solving GCSPs have to deal with rigidity; e.g., geometric decompositions produce sequences of rigid subGCSPs to be solved separately and then assembled. .

The techniques used for rigidity detection can be classi­ fied in two categories: pattern-based approaches [Bouma et al., 1995; Kramer, 1992] depend on a repertoire of rigid bodies of known shape which cannot cover all practical instances; flow-based approaches [Hoffmann et al., 1997; Lamure and Michelucci, 1998] use flow (or maximum match­ ing) machinery to identify subGCSPs verifying the structural rigidity, a property based on a degree of freedom count.

The latter approaches are more general eventhough struc­ tural rigidity is only an approximation of rigidity. Heuristics,

Bertrand Neveu and Gilles Trombettoni

COPRIN Team, INRIA-BS/CNRS-CERMICS, 2004 route des lucioles, BP 93, 06902 Sophia Antipolis, France

e-mail: Bertrand. Neveu®sophia . inria. fr ,

Gilles.Trombettoni®sophia . inria.fr

like ad-hoc geometric rules, have been proposed to enhance structural rigidity capabilities, none of which succeeded to cover the gap between structural rigidity and rigidity. In [Jer­ mann et al., 2002], we have defined the extended structural rigidity, a new approximation of rigidity which supersedes even the heuristically enhanced characterizations.

In this paper, we focus on the algorithmic aspects of the structural characterization of rigidity. [Hoffmann eta!. , 1997] have proposed a flow-based algorithm called Dense for this purpose. After providing the necessary background (Sec­ tion 2), we exemplify the limits of this algorithm and the ca­ pabilities of our new algorithm (Section 3). Section 4 presents the specificities of our new algorithm and explains its advan­ tages: it uses the extended structural rigidity instead of the structural rigidity and it is designed in a geometrically cor­ rect way. To conclude, we explain how this algorithm can be used to tackle the major issues related to rigidity.

2 Background

This section provides the necessary background for the pa­ per. It formally defines GCSPs, the rigidity concept and the structural characterizations of rigidity.

2.1 Geometric Constraint Satisfaction Problems

Definition 1 GCSP

A geometric constraint satisfaction problem (GCSP) S = ( 0 , C) is defined by a set 0 of geometric objects and a set C of geometric constraints binding its objects.

S' = (0', C') is a subGCSP ofS = (0, C) (noted S' c S) if!O' C 0 and C' = { c E Clc binds only objects in 0'} (i.e., S' is induced by 0').

Fig. 1-a presents a GCSP in 2D composed of 3 lines con­ strained by 2 parallelisms and 2 line-line distances; Fig. 1-b depicts a GCSP in 3D composed of 1 line and 5 points bound by 4 point-line incidences and 5 point-point distances.

We assume that geometric objects are indeformable (e.g., no circle with variable radius). Also geometric constraints must involve only positions and orientations of the objects and they must be independent from the global reference sys­ tem (i.e., constraints only fix objects relatively one to an­ other). These limitations make the structural characteriza­ tions of rigidity easier and are mandatory for geometric solv­ ing methods based on rigidity.

According to these restrictions, a solution to a GCSP S = ( 0, C) is composed of one position and orientation for each object in 0 and satisfies all the constraints in C. For the solv­ ing purpose, a GCSP is translated into a system of equations: each object is represented by a set of unknowns (over the re­ als) which determine its position and orientation; each con­ straint becomes a system of equations on the unknowns of the objects it constrains.

2.2 Rigidity

Rigidity is defined w.r.t. movements. A movement in a GCSP is either a deformation (if it does not preserve the relative positions of the objects) or a displacement (rota­ tion+translation). Intuitively, a GCSP is rigid if it admits no deformation, and all the displacements of the geometric space. It is under-rigid if it admits some deformations, and over-rigid if it does not admit some displacements or has no solution. More formal definitions of rigidity can be found in [Whiteley, 1987].

In Fig. 1-b, the subGCSP CDF is rigid since a triangle is indeformable and admits all translations and rotations in 3D. The subGCSP AF is under-rigid: point F can move indepen­ dently of line A since there is no constraint between them. The subGCSP ACDEF is over-rigid since it has no solution: generically, it is impossible to place a point at the intersection of the 3 spheres(= 3 distance constraints) which centers are aligned.

2.3 Structural Rigidity

The structural rigidity corresponds to an analysis of degrees of freedom (DOF) in a GCSP. Intuitively, one DOF represents one independent movement in a GCSP. More formally:

Definition 2 Degree of freedom (DOF)

• Object o: DOF(o) is the number of independent parameters used to determine the position and the orientation of o.
• Constraint c: DOF(c) is the number of independent equa­ tions in the subsystem of equations representing c.
• GCSP S = (0, C): DOF(SJ="L 0 DOF(o)- "LcDOF(c).

In 3D, points have 3 DOFs, lines have 4 DOFs; point-line incidences remove 2 DOFs, and point-point distances remove 1 DOF. Thus, subGCSPs ACD, CDF and AF from the GCSP in Fig. 1-b have respectively 5, 6 and 7 DOFs.

Structural rigidity is a generalization of Laman's theo­ rem [Laman, 1970 ], which characterizes generic rigidity of 2D bar frameworks. It is based on the following intuition: if a GCSP admits less (resp. more) movements than the num­ ber of independent displacements in the considered geometric space (which is d(dil) in dimension d), then it is over-(resp. under-)rigid.

Definition 3 Structural rigidity (s_rigidity)

A GCSP S = ( 0, C) in dimension d is s_rigid iff DOF(S) = d(dil) and'VS' c S, DOF(S') 2: d(dil)·

Sis under-s_rigid iff DOF(S) > d(dil) and contains no over­ s_rigid subGCSP

Sis over-s_rigid iff3S' ~ S, DOF(S') < d(dil).

In practice, structural rigidity is considered a good ap­ proximation of rigidity [Lamure and Michelucci, 1998; Hoff­ mann eta!., 1997]. However, the gap between rigidity and s_rigidity is in fact significant (see [Jermann et al., 2002]). We illustrate the difference on two subGCSPs from Fig. 1b: ABCD is s_rigid in 3D since DOF(ABCD)=6; it is in fact under-rigid since point B can move independently of segment CD along line A. ACDE is over-s_rigid since DOF(ACDE)=5, but it is in fact well-rigid.

2.4 Extended Structural Rigidity

The extended structural rigidity (es_rigidity in short) is based on the degree of rigidity (DOR) concept. The DOR of a sub­ GCSP is the number of independent displacements it admits; it depends on the geometric properties it verifies. For exam­ ple, the DOR of two lines in 2D is 3 if they are not parallel, 2 if they are parallel; the parallelism property can be an explicit constraint, but it can also be induced by the constraints of the GCSP embedding these lines. In this second case, computing the DOR may be equivalent to geometric theorem proving.

The principle behind the extended structural rigidity is the following: a GCSP is rigid if all its movements are displace­ ments. Hence, comparing its DOF to its DOR allows us to determine if it admits movements (DOF) which are not dis­ placements (DOR), i.e., deformations.

Definition 4 Extended Structural Rigidity (es_rigidity)

• A GCSP S = ( 0, C) in dimension d is es_rigid iff DOF(S)=DOR(S) and'VS' c S, DOF(S')2:DOR(S').
• S is under-es_rigid iff DOF(S) > DOR(S) and contains no over-es_rigid subGCSP

Sis over-es_rigid iff3S' ~ S, DOF(S')<DOR(S').

The es_rigidity is superior to the s_rigidity (e.g., es_rigidity exactly corresponds to rigidity on every subGC­ SPs in Fig. 1). See [Jermann et al., 2002] for a comparison between s_rigidity and es_rigidity and details about the DOR concept.

2.5 Object-Constraint Network

A GCSP S = (0, C) can be transformed into an object­ constraint network G = (s, V, t, E, w). Fig. 2-a depicts the object-constraint network of the GCSP presented in Fig. 1-a. A flow in this network (introduced in [Hoffmann eta!., 1997]) represents a distribution of the DOFs of the constraints onto the DOFs of the objects. This is why flow computation is used to perform the DOF analysis which is at the basis of structural characterization of rigidity: in Section 4, we will explain how this network is used for s_rigidity ([Hoffmann et al., 1997]'s Dense algorithm) and es_rigidity (our new algorithm).

Definition 5 Object-Constraint Network (s, V, t, E, w)

• s is the source and t is the sink.
• -Each object o E 0 becomes an object-node V 0 E V .
• -Each constraint c E C becomes a constraint-node Vc E V .
• -For each object o E 0 there is an arc V 0 --> T of capacity w(v0 --> T) =DOF(o) in E.
• For . each constraint c E C, there is an arc S --> Vc of capacity w(S--> vc) =DOF(c) in E.
• -For each object o E 0 constrained by c E C there is an arc Vc ____. V 0 of capacity w( Vc --> V 0 ) = oo in E.

3 Overview

In this section, we exemplify the contribution presented in this paper on the GCSPs in Fig. 1. We illustrate the two main differences between algorithm Dense and our algorithm:

1. In our algorithm, the overflow depends on the geometric properties of the objects it is applied to, while it depends only on the dimension of the geometric space in Dense.
2. In our algorithm, the overflow is applied via a dedicated node R which can be attached to any subset of objects, while it is applied directly via one constraint-node in Dense.

Example 1

The first example (Fig. 1-a; in 20) highlights the first differ­ ence. Fig. 2-a presents the object-constraint network associ­ ated to this GCSP. In this picture, one can see the overload K = 3 applied on the first constraint by algorithm Dense. This constraint is linked to two lines, A and B, which are parallel and lie at prescribed distance in the plane; AB is a rigid subGCSP. However, one can easily see that the overload cannot be distributed completely since a capacity 5 (two con­ straints plus the overload) is applied to two lines having only 4 DOFs. Hence, the GCSP is identified as over-rigid since it contains a sub-GCSP with less than 3 OOFs.

Fig. 2-b displays our algorithm behavior when the virtual constraint R is linked to the same subGCSP, AB. The value of the overflow K is computed according to the geometric properties of these lines: since they are parallel, K = 2 (in­ stead of 3 in algorithm Dense). Thus, the flow can be satu­ rated: a capacity 4 (two constraints plus the overflow) exactly matches the 4 OOFs of AB; the GCSP is not identified over­ rigid by our algorithm. Further overflow applications would allow to identify the GCSP as well-rigid.

Example 2

The second example (Fig. 1-b; in 30) illustrates the second difference. Its object-constraint network is depicted in Fig. 2d. This figure shows the application of an overflow 6 via the virtual constraint R onto the 3 points C, E and F by our algo­ rithm; the overflow cannot be distributed completely, which signals an over-rigid subGCSP: ACDEF, found by adding reachable objects from R in the residual graph.

Algorithm Dense applies the overflow directly through a constraint-node. Since all constraints are binary in this exam­ ple, Dense cannot apply an overflow to the same set of ob­ jects as our algorithm. More generally, Dense cannot apply the overflow to all subGCSPs and can miss rigid or over-rigid ones. Moreover, applying the overflow 6 to a pair of objects in this GCSP leads to an incorrect answer, as it was the case in the previous example; e.g., segments which are rigid would be identified over-rigid.

These examples show that some simple and very common subGCSPs in 20 and 30, like parallel lines, triangles or seg­ ments, cannot be treated correctly by algorithm Dense 1 .

In the following section, we detail the differences between algorithm Dense and our new algorithm and we present their consequences.

4 Algorithms

In this section, we present Hoffmann et a!. 's Dense algo­ rithm in comparison to our new algorithm. Both use flow machinery on the object-constraint network representing the GCSP. Our algorithm has two main differences with algo­ rithm Dense:

• It uses es_rigidity instead of s_rigidity.
• It distributes flow in a geometrically correct way in the network.

These new features are achieved thanks to two major mod­ ifications in the Distribute function used by Dense (see beginning of Section 3).

We introduce first the principle of flow-based character­ ization of rigidity; then we present and discuss function Distribute which is the key to our contribution. Finally we explain how this function is used to design algorithms for the main problems related to rigidity.

4.1 Flow-based Rigidity Detection

From the geometric point of view, the principle of structural characterization of rigidity is to check if a GCSP admits only displacements. Hence, flow-based rigidity identification can be understood as follows:

1 In practice [Sitharam, 2000], Dense embeds heuristic rules to prevent this kind of simple failures, but more complicated examples can still mistake the algorithm since no rule-based approach can han­ dle all the singular cases.

1. remove K displacements from the GCSP by introducing K DOFs on the constraint side;
2. check if an over-constrained subGCSP S' exists by computing a maximum flow in the overloaded object­ constraint network;
3. if so S' verifies DOF(S')<K.

Indeed, a maximum flow in the object-constraint network represents an optimal distribution of the DOFs of the con­ straints among the DOFs of the objects. If it does not satu­ rate all the arcs outgoing from the source, some constraints' DOFs cannot be absorbed by the objects, i.e., the GCSP is over-constrained. In this case, there exists a subGCSP S' such that DOF(S')<O. When an overflow K is applied in the network on the constraint side, the identified subGCSP S' verifies DOF(S')<K. [Hoffmann eta/., 1997] have proven that S' is then induced by the objects traversed during the last search for an augmenting path, i.e. , by the objects reachable from the overloaded constraint-node in the residual graph.

Depending on the value of K, this principle can be applied to identify s_rigid (K = d(di 1 ) + 1), over-s_rigid (K = d(di 1 l), es_rigid (K = DOR + 1) or over-es_rigid (K = DOR) subGCSPs.

4.2 Function Distribute

Function Distribute [Hoffmann eta/., 1997] implements the principle presented above. We present our version of this function and explain why and how it differs from Hoffmann eta/. 's one.

As already said, applying an overflow K corresponds, from the geometric point of view, to removing K displacements from the objects linked to this constraint. But nothing ensures that the subGCSP linked to a single constraint allows K inde­ pendent displacements: removing K DOFs from a subGCSP S' with DOR(S')<K is geometrically incorrect 2 .

For instance, consider a subGCSP composed of 2 points linked by a point-point distance in 3D. This GCSP allows only 5 of the 6 independent displacements (3 rotations + 3 translations) of the 3D space since they lack the rotation around the line going through them. Therefore, removing 6 displacements from a couple of points is geometrically in­ correct. However, Hoffmann eta/. 's function Distribute does so when the distance constraint binding the two points in 3D is overloaded with K = 6.

In order to distribute the flow in a geometrically correct way, we propose to introduce a fictive constraint R, having DOF(R)=K. This constraint can be linked only to subset of objects 0' allowing K independent displacements, i.e. induc­ ing a subGCSP S' having DOR(S')2: K. K and S' are two parameters of our function Distribute.

Function Overloaded-Network returns the object­ constraint network corresponding to S where the fictive con­ straint R, set with capacity K , is linked to the objects of S'. The maximum flow computation is achieved by a standard flow algorithm 3 like FordFulkerson [Ford and Fulkerson, 1962]. This function returns the set V of objects reachable from the virtual constraint R in the residual graph if the max­ imum flow cannot distribute the whole overload, an empty set V otherwise. Function Object- Induced- subGCSP returns the subGCSP S" induced by V. S" verifies DOF(S")<K or S" is empty.

2 Remember that the DOR represents the number of independent displacements admitted by a subGCSP.

Distribute (S: GCSP; K : integer; S': GCSP) returns S": GCSP)

Require: K > 0, S' C S verifies DOR(S')2: K

Ensure: S" C S verifies DOF(S")< K, or S" is empty

G +- Overloaded-Network(S, K , S')

V +- FordFulkerson(G)

S" +-Object- Induced- subGCSP(V, S)

ReturnS"

The two differences between our version of the Distribute function and Hoffmann eta/. 's version have already been mentioned: the use of a dedicated constraint for overflow distribution, which allows to distribute the overflow to any subset of objects; and the adaptation of the overflow to the set of objects on which it is applied, which renders over­ flow application geometrically correct.

Example: The call to Distribute ( S, 3, dAB) (Hoff­ mann et al.'s version) for the GCSP in Fig. 1-a is presented in Fig. 2-a. Since the overflow cannot be fully distributed, the subGCSP AB is returned. This is correct from the flow point of view since DOF(AB)=2 is less than K = 3. However, from the geometric point of view, it is incorrect to interpret this result as an over-rigidity in the GCSP.

For the same subGCSP, our Distribute function is called differently: since DOR(AB)=2, the overflow can be at most 2. Fig. 2-b presents the call to Distribute (S, 2, AB) . The overflow can be distributed fully: no subGCSP is returned. Further similar calls would allow to conclude that this GCSP is not over-rigid.

Time Complexity: The complexity of our func­ tion Distribute is dominated by that of function FordFulkerson; it is O(n 2 (n + m)) where n is the number of nodes and m the number of arcs. It is strictly equivalent to the complexity of Hoffmann eta/. 's version.

Note that if several calls to this function are performed, it could be modified to compute maximum flow in an incremental way, yielding a better complexity.

4.3 Algorithms For Rigidity Detection

Based on the Distribute function, several algorithms can be designed to tackle the major problems related to the rigid­ ity concept. [Hoffmann et a/., 1997] have proposed the Dense and Minimal_Dense algorithms to identify a well or over-rigid subGCSP and minimize it (using a classical lin­ ear minimization process). These algorithms can be repro­ duced using our function Distribute. This allows us to tackle the same problems in a geometrically correct manner and with a better characterization of rigidity: the extended structural rigidity. We will show on algorithm Dense how to introduce our Distribute function in existing algorithms.

3 In [Hoffmann et al., 1997], function Distribute is specifi­ cally designed for binary constraints and flow distribution is merged with network construction and subGCSP identification.

Algorithm Dense Versus Algorithm Over-Rigid

Schematically, algorithm Dense operates by calling the Distribute function for each constraint in the GCSP until a non-empty subGCSP is returned. The overload is induced by the dimension of the considered geometric space: it rep­ resents the maximum number of independent displacements in this space (3 in 2D, 6 in 3D). Dense is supposed to re­ turn only over-rigid subGCSPs since returned GCSPs do not admit all the displacements allowed by the considered geo­ metric space.

In fact, Dense is incorrect since it may remove more DOFs than the number of displacements admitted by a sub­ GCSP. For instance, two parallel lines admit only 2 displace­ ments in 2D; hence, removing 3 displacements from two par­ allellines is geometrically incorrect in 2D.

To obtain a geometrically correct version of algorithm Dense, we propose to use the es_rigidity instead of the s_rigidity, i.e. the DOR is the overload; also, we use our Distribute function instead of Hoffmann eta!. 's one.

This results in a new algorithm, called Over-Rigid which performs one call to function Distribute (S, DOR (S'), S')) for each S' C S to iden­ tify over-es_rigid subGCSPs. Indeed, if the call for a givenS' returns a non-empty subGCSP S", then it verifies DOF(S") < DOR(S'), a sufficient condition for being over-es_rigid (see Def. 4). Unfortunately, the number of subGCSPs is exponential, which would lead to an exponential number of calls to function Distribute. However, we will show that it is sufficient and correct to apply this function only to the DOR-minimal subGCSPs (see Def. 6 below), which gives the following algorithm:

Over-Rigid (S: GCSP) returns S": GCSP

Ensure: S" c S is over-es_rigid or empty S" <- EmptyGCSP

M <- DOR-Minimals (S) {builds the set M of all DOR-minimal subGCSPs inS}

whileS"= EmptyGCSP and M =f. 0 do

S' <- Pop(M)

S" <-Distribute (S, DOR (S') , S')

end while ReturnS"

Definition 6 DOR-minimal subGCSP

A subGCSP S' in a GCSP S is DOR-minimal if it contains no proper subGCSP with the same DOR, i.e. 'v'S" C S', DOR(S")<DOR(S'). -

Example of over-Rigid application

Consider again the GCSP S presented in figure 1-b. Let M = {BC,BDF,CEF, ... } be the set ofDOR-minimal subGCSPs generated by DOR-Minimals ( S ) . Algorithm Over-Rigid then proceeds as follows:

1. First turn, S' = BC and K =DOR(BC)=5. Fig. 2(c) represents the call to Distribute ( S, 5, BC). All the arcs outgoing from the source being saturated, no over­ es_rigid subGCSP is identified.
2. At this tum, S' = CEF and K =DOR(CEF)=6. The call to Distribute ( S , 6, CEF) is represented in fig­ ure 2(d). This turn, the arcS--+ R is unsaturated. Since the set of object-nodes traversed during the last search for an augmenting path is {A, C, D, E, F}, the identi­ fied subGCSP is ACDEF which is over-es_rigid.

On the same example, algorithm Dense would identify each segment (2 points + 1 distance) and each point on the line A as an over-rigid subGCSP, which is false.

Properties of algorithm Over-Rigid

To prove the correctness and completeness of algorithm Over-Rigid, we need the following lemmas which estab­ lish properties on the DOR concept and onJiow distribution:

Lemma 1 Let S be a GCSP and S' C S" C S two subGC­ SPs. Then DOR(S') :::; DOR(S").

Proof Each unit of DOR in a GCSP represents an indepen­ dent displacement (translation or rotation). Adding a new object o with some constraints to a subGCSP S' cannot re­ move the independent displacements already granted to S' since constraints are independent from the global reference system. Thus, DOR(S'):::; DOR(S' U {o}).D

Lemma 2 Let S" C S' C S be two nested subGCSPs in a GCSP S. If the call to Distribute(S,K,S') returns a non-empty subGCSP So. then a call to Distribute (S, K, S") returns a non-empty subGCSP S1.

Proof Let G s· be the object-constraint network overloaded for S' and G S" the network overloaded for S". The only difference between these two networks resides in the fact that there are more arcs of the type R --+ o in G S'· Thus, it is more difficult to distribute an overflow in G S" than in G S': if a maximum flow in G S' cannot saturate all the arcs outgoing from the source, a maximum flowinG S" cannot either.D

We will now prove the completeness, correctness and dis­ cuss the time complexity of our algorithm.

Correctness of Over-Rigid:

Let S" be a non-empty subGCSP resulting from Over-Rigid(S). Assuming it has been returned by the call to Distribute(S, DOR(S'), S'), S" must verify DOF(S") < DOR(S') since S" is not empty. More­ over, by design of function Distribute, S' C S". Since Lemma 1 implies that DOR(S'):SDOR(S"), we can ensure that if S" is not empty, then DOF(S")<DOR(S"), i.e., S" is over-es_rigid. D

Completeness of Over-Rigid:

Algorithm Over-Rigid applies an overload only for each element in the set M of all DOR-minimal subGCSPs (computed by DOR-Minimals ( S) ) . Lemma 2 ensures that it is sufficient to distribute an overload for each DOR-minimal subGCSP, since any non DOR-minimal subGCSP contains, by definition, DOR-minimal subGCSPs.D

Time Complexity of Over-Rigid:

The complexity of algorithm Over-Rigid depends on the number of DOR-minimal subGCSPs. We have proven by enumeration that the number of objects in a DOR-minimal subGCSP is 2 in 2D and 3 in 3D for GCSPs including points, lines and planes constrained by distances, angles, incidences and parallelisms. Thus, for GCSPs in this class, the number ofDOR-minimal subGCSPs is O(nd) where n is the number of objects and d the dimension of the geometric space (2 or 3).

Let us call 0 1 the complexity of function DOR-Minimals, and 02 that of function Distribute, discussed in the previous section. Then, the worst-case complexity of algorithm Over-Rigid is 0(01 + nd * 02).

01 is generally the complexity of geometric theorem prov­ ing, i.e., it is exponential. However, in some practical classes of GCSPs, like mechanisms or bar frameworks, it is polyno­ mial or even constant. Moreover, heuristic DOR computation can be used when geometric theorem proving is required but not affordable. In these cases, 0 1 can be neglected in com­ parison to 0 2 . We end up with O(nd+ 2 * (n + m)). In com­ parison, the complexity of algorithm Dense is O(m * n 2 * (n + m)). Thus, the overhead to obtain a geometrically cor­ rect algorithm is approximately linear in 2D, and quadratic in 3D.

4.4 Other algorithms

Function Distribute can be used in a similar way to tackle the major problems related to rigidity: identifying rigid subGCSPs (just by changing the value of the overflow in al­ gorithm Over-Rigid), deciding if a GCSP is rigid (by one call to Over-Rigid and a DOF count), finding a minimal well­ or over-rigid subGCSP (by classical minimization step, as in Minimal Dense). For all these problems, using our new algorithms-and the es_rigidity instead of the s_rigidity leads to geometrically correct and more reliable algorithms.

4.5 Conclusion

The new design of function Distribute allows a more general use of this function: the flow distribution is now performed in a geometrically sound marmer and allows for checking a better characterization of rigidity. The DOR­ minimal concept and its properties have appeared to be the key to obtain a new family of polynomial algorithms for the major problems related to rigidity.

These new algorithms can handle GCSPs in 2D and 3D correctly with respect to the es_rigidity. They can handle GC­ SPs with constraints like parallelism or incidence, which was not possible with Hoffmarm eta/. 's algorithms. Indeed, these constraints introduce geometric properties in GCSPs, leading to subGCSPs with a DOR different from the number of in­ dependent displacements in d-space. This kind of constraints are ubiquitous in practical applications (architecture, CAD, mechanisms) and our new algorithms open a way for reliable industrial use in these domains.