Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/86309
Título:
|
Decomposition of geometric constraint graphs based on computing fundamental circuits
|
Autor/a:
|
Joan Arinyo, Robert; Soto Riera, Antoni; Tarres Puertas, Marta Isabel; Vila Marta, Sebastià
|
Otros autores:
|
Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics |
Abstract:
|
The graph-based geometric constraint solving technique works in two steps. First the geometric problem is translated into a graph whose vertices represent de set of geometric elements and whose edges are the constraints. Then the constraint problem is solved by decomposing the graph into a colection of subgraphs each representing a standard problem which is solved by a dedicated equational solver. In this work we report on an algorithm to decompose biconnected graphs representing geometric constraint problems. The algorithm is based on recursively splitting the graphs through terns of vertices located on fundamental circuits of the graph. Preliminar experiments suggest that the algorithm runtime is at worst quadratic with the total number of vertices in the graph. In a case study we illustrate how the algorithm works. |
Materia(s):
|
-Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica -Geometric constraint solving -Graph decomposition |
Derechos:
|
|
Tipo de documento:
|
Artículo - Versión publicada Informe |
Compartir:
|
|
Mostrar el registro completo del ítem