Revisiting decomposition analysis of geometric constraint graphs

Geometric problems defined by constraints can be represented by geometric constraint graphs whose nodes are geometric elements and whose arcs represent geometric constraints. Reduction and decomposition are techniques commonly used to analyze geometric constraint graphs in geometric constraint solvi...

Full description

Saved in:
Bibliographic Details
Published in:Computer aided design 2004-02, Vol.36 (2), p.123-140
Main Authors: Joan-Arinyo, R., Soto-Riera, A., Vila-Marta, S., Vilaplana-Pastó, J.
Format: Article
Language:English
Subjects:
Constraint solving
Geometric constraints
Graph-based constraint solving
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Geometric problems defined by constraints can be represented by geometric constraint graphs whose nodes are geometric elements and whose arcs represent geometric constraints. Reduction and decomposition are techniques commonly used to analyze geometric constraint graphs in geometric constraint solving. In this paper we first introduce the concept of deficit of a constraint graph. Then we give a new formalization of the decomposition algorithm due to Owen. This new formalization is based on preserving the deficit rather than on computing triconnected components of the graph and is simpler. Finally we apply tree decompositions to prove that the class of problems solved by the formalizations studied here and other formalizations reported in the literature is the same.
ISSN:0010-4485
1879-2685
DOI:10.1016/S0010-4485(03)00057-5