zbMATH — the first resource for mathematics

Detecting all dependences in systems of geometric constraints using the witness method. (English) Zbl 1195.68107
Botana, Francisco (ed.) et al., Automated deduction in geometry. 6th international workshop, ADG 2006, Pontevedra, Spain, August 31–September 2, 2006. Revised papers. Berlin: Springer (ISBN 978-3-540-77355-9/pbk). Lecture Notes in Computer Science 4869. Lecture Notes in Artificial Intelligence, 98-112 (2007).
Summary: In geometric constraints solving, the detection of dependencies 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 dependencies due to geometric theorems and to decompose such systems. In this paper, we discuss why detecting all dependencies between constraints is a hard problem and propose to use the witness method published recently to detect both structural and non-structural dependencies. We study various examples of constraints systems and show the promising results of the witness method in subtle dependencies detection and systems decomposition.
For the entire collection see [Zbl 1132.68006].

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68U07 Computer science aspects of computer-aided design
Full Text: DOI