ANewStructuralRigidityforGeometricConstraintSystems.PDFVIP

A New Structural Rigidity for Geometric Constraint Systems Christophe Jermann , Bertrand Neveu , and Gilles Trombettoni Christophe.Jermann@epfl.ch AI Lab, EPFL, 1015 Lausanne, Switzerland {Bertrand.Neveu, Gilles.Trombettoni}@sophia.inria.fr COPRIN Team, INRIA-I3S-CERMICS, 2004 route des lucioles, BP 93, 06902 Sophia.Antipolis, France Abstract. The structural rigidity property, a generalization of Lamans theorem which characterizes rigid bar frameworks in 2D, is generally considered a good heuristic to detect rigidities in a geometric constraint satisfaction problem (GCSP). The gap between rigidity and structural rigidity essentially resides in the fact that structural rigidity is not a geometric property. In this article, we propose a new denition of structural rigidity which takes into account geometric aspects of rigidity. We also propose a new ow-based algorithm for identifying GCSPs verifying our new denition. This algorithm works on a geometric constraint network introduced by Homann et al. 1 Introduction Geometric constraint satisfaction problems arise naturally in several areas, such as architecture, design of mechanisms and molecular biology. The rigidity con- cept is in the heart of many of these problems: deciding whether a geometric constraint satisfaction problem (GCSP) is rigid or not, detecting rigid sub-parts, detecting over-rigid sub-parts, and so on. Several solving methods [Kra92,BFH 95,LM97,DMS97,HLS00,JTNR00] for GCSPs have to handle rigidity related problems. In particular, recursive rigidi- cation techniques decompose a GCSP into a sequence of rigi