6533b85afe1ef96bd12b8cd6

RESEARCH PRODUCT

Interrogating witnesses for geometric constraint solving

Dominique MichelucciSebti Foufou

subject

0209 industrial biotechnologyMathematical optimizationGeometric constraintsTheoretical computer science[ INFO.INFO-NA ] Computer Science [cs]/Numerical Analysis [cs.NA]InfinitesimalComputationRigidity (psychology)02 engineering and technologyTheoretical Computer ScienceDependent and independent constraintsGeometric networks020901 industrial engineering & automation0202 electrical engineering electronic engineering information engineeringConstraint solvingMathematicsGeometric transformationWitness configuration020207 software engineering[INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA]16. Peace & justiceWitnessComputer Science ApplicationsComputational Theory and MathematicsConstraint decompositionGraph (abstract data type)Infinitesimal motionsAlgorithmInformation SystemsVector space

description

International audience; Classically, geometric constraint solvers use graph-based methods to decompose systems of geometric constraints. These methods have intrinsic limitations, which the witness method overcomes; a witness is a solution of a variant of the system. This paper details the computation of a basis of the vector space of free infinitesimal motions of a typical witness, and explains how to use this basis to interrogate the witness for dependence detection. The paper shows that the witness method detects all kinds of dependences: structural dependences already detectable by graph-based methods, but also non-structural dependences, due to known or unknown geometric theorems, which are undetectable by graph-based methods. It also discusses how to decide about the rigidity of a witness and how to decompose it.

yearjournalcountryeditionlanguage
2012-07-01
https://hal.archives-ouvertes.fr/hal-00784001