6533b853fe1ef96bd12ac070

RESEARCH PRODUCT

Detecting All Dependences in Systems of Geometric Constraints Using the Witness Method

Dominique MichelucciSebti Foufou

subject

Mathematical optimizationStructural dependenceGraph (abstract data type)Geometric theoremAlgorithmWitnessMathematics

description

In geometric constraints solving, the detection of dependences and the decomposition of the system into smaller subsystems are two important steps that characterize any solving process, but nowadays solvers, which are graph-based in most of the cases, fail to detect dependences due to geometric theorems and to decompose such systems. In this paper, we discuss why detecting all dependences between constraints is a hard problem and propose to use the witness method published recently to detect both structural and non structural dependences.We study various examples of constraints systems and show the promising results of the witness method in subtle dependences detection and systems decomposition.

yearjournalcountryeditionlanguage
2007-12-06
https://doi.org/10.1007/978-3-540-77356-6_7