Interrogating witnesses for geometric constraint solving

Sebti Foufou, Dominique Michelucci

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)24-38
Number of pages15
JournalInformation and Computation
StatePublished - Jul 2012


  • Constraint decomposition
  • Constraint solving
  • Dependent and independent constraints
  • Geometric constraints
  • Infinitesimal motions
  • Witness configuration

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'Interrogating witnesses for geometric constraint solving'. Together they form a unique fingerprint.

Cite this