Title:
|
Revisiting decomposition analysis of geometric constraint graphs
|
Author:
|
Joan Arinyo, Robert; Soto Riera, Antoni; Vila Marta, Sebastià; Vilaplana Pastó, Josep
|
Other authors:
|
Universitat Politècnica de Catalunya. Departament d'Enginyeria Minera, Industrial i TIC; Universitat Politècnica de Catalunya. Departament de Ciències de la Computació |
Abstract:
|
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 {em 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. |
Subject(s):
|
-Àrees temàtiques de la UPC::Informàtica -Decomposition analysis -Geometric constraint -Constraint solving -Graph-based constraint solving |
Rights:
|
|
Document type:
|
Article - Published version Report |
Share:
|
|