Numerical decomposition of geometric constraints

Sebti Foufou, Dominique Michelucci, Jean Paul Jurzak

Research output: Contribution to journalConference articlepeer-review


Geometric constraint solving is a key issue in CAD/CAM. Since Owen's seminal paper, solvers typically use graph based decomposition methods. However, these methods become difficult to implement in 3D and are misled by geometric theorems. We extend the Numerical Probabilistic Method (NPM), well known in rigidity theory, to more general kinds of constraints and show that NPM can also decompose a system into rigid subsystems. Classical NPM studies the structure of the Jacobian at a random (or generic) configuration. The variant we are proposing does not consider a random configuration, but a configuration similar to the unknown one. Similar means the configuration fulfills the same set of incidence constraints, such as collinearities and coplanarities. Jurzak's prover is used to find a similar configuration.

Original languageEnglish (US)
Pages (from-to)143-151
Number of pages9
JournalACM Symposium on Solid Modeling and Applications, SM
StatePublished - 2005
EventSPM 2005 - ACM Symposium on Solid and Physical Modeling - Cambridge, MA, United States
Duration: Jun 13 2005Jun 15 2005


  • Constraints decomposition and solving
  • Geometric constraints
  • Geometry provers

ASJC Scopus subject areas

  • General Engineering


Dive into the research topics of 'Numerical decomposition of geometric constraints'. Together they form a unique fingerprint.

Cite this