INCIDENCE CONSTRAINTS: A COMBINATORIAL APPROACH

The simplest geometric constraints are incidences between points and lines in the projective plane. This problem is universal, in the sense that all algebraic systems reduce to such geometric constraints. Detecting incidence dependences between these geometric constraints is NP-complete. New methods to prove incidence theorems are proposed, which use strictly no computer algebra but only combinatorial arguments.

Special track on Geometric Constraints and Reasoning

Geometric Computing and Reasoning (GCR) aims at emphasizing recent trends in the domain of geometric constraint solving and automated, or computer aided deduction in geometry. This year sees the third edition of this technical track of SAC.

Session details: Geometric computing and reasoning (GCR)

Session details: Geometric computing and reasoning

Editorial message

Geometric Computing and Reasoning (GCR) is a new track of SAC and it is dedicated to the recent trends in the domain of geometric constraint solving and automated, or computer aided, deduction in geometry.

Session details: Geometric constraints and reasoning

Using the witness method to detect rigid subsystems of geometric constraints in CAD

International audience; This paper deals with the resolution of geometric constraint systems encountered in CAD-CAM. The main results are that the witness method can be used to detect that a constraint system is over-constrained and that the computation of the maximal rigid subsystems of a system leads to a powerful decomposition method. In a first step, we recall the theoretical framework of the witness method in geometric constraint solving and extend this method to generate a witness. We show then that it can be used to incrementally detect over-constrainedness. We give an algorithm to efficiently identify all maximal rigid parts of a geometric constraint system. We introduce the algorit…

Extensions of the witness method to characterize under-, over- and well-constrained geometric constraint systems

International audience; This paper describes new ways to tackle several important problems encountered in geometric constraint solving, in the context of CAD, and which are linked to the handling of under- and over-constrained systems. It presents a powerful decomposition algorithm of such systems. Our methods are based on the witness principle whose theoretical background is recalled in a first step. A method to generate a witness is then explained. We show that having a witness can be used to incrementally detect over-constrainedness and thus to compute a well-constrained boundary system. An algorithm is introduced to check if anchoring a given subset of the coordinates brings the number …