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!
cited_by cdi_FETCH-LOGICAL-c416t-4fda2e5ec20ea43077ebcbf4b96790ae7ecf1b1f32c55db9f1b939d898f743e63
cites cdi_FETCH-LOGICAL-c416t-4fda2e5ec20ea43077ebcbf4b96790ae7ecf1b1f32c55db9f1b939d898f743e63
container_end_page 140
container_issue 2
container_start_page 123
container_title Computer aided design
container_volume 36
creator Joan-Arinyo, R.
Soto-Riera, A.
Vila-Marta, S.
Vilaplana-Pastó, J.
description 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.
doi_str_mv 10.1016/S0010-4485(03)00057-5
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_miscellaneous_28752592</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>S0010448503000575</els_id><sourcerecordid>28347824</sourcerecordid><originalsourceid>FETCH-LOGICAL-c416t-4fda2e5ec20ea43077ebcbf4b96790ae7ecf1b1f32c55db9f1b939d898f743e63</originalsourceid><addsrcrecordid>eNqNkEtLxDAUhYMoOI7-BKEr0UU1z6ZZqQy-YEDwsQ5pejNG2qYmnYH593ZmxK2uLge-c-B-CJ0SfEkwKa5eMSY457wU55hdYIyFzMUempBSqpwWpdhHk1_kEB2l9DlClDA1QTcvsPLJD75bZDXY0PZhk0KXmc406-RTFly2gNDCEL3NbOjSEI3vhmwRTf-RjtGBM02Ck587Re_3d2-zx3z-_PA0u53nlpNiyLmrDQUBlmIwnGEpobKV45UqpMIGJFhHKuIYtULUlRqDYqouVekkZ1CwKTrb7fYxfC0hDbr1yULTmA7CMmlaSkGFov8AGZcl5SModqCNIaUITvfRtyauNcF6I1ZvxeqNNY2Z3orVYuxd73owvrvyEHWyHjoLtY9gB10H_8fCN-rjgSI</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>28347824</pqid></control><display><type>article</type><title>Revisiting decomposition analysis of geometric constraint graphs</title><source>ScienceDirect Journals</source><creator>Joan-Arinyo, R. ; Soto-Riera, A. ; Vila-Marta, S. ; Vilaplana-Pastó, J.</creator><creatorcontrib>Joan-Arinyo, R. ; Soto-Riera, A. ; Vila-Marta, S. ; Vilaplana-Pastó, J.</creatorcontrib><description>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.</description><identifier>ISSN: 0010-4485</identifier><identifier>EISSN: 1879-2685</identifier><identifier>DOI: 10.1016/S0010-4485(03)00057-5</identifier><language>eng</language><publisher>Elsevier Ltd</publisher><subject>Constraint solving ; Geometric constraints ; Graph-based constraint solving</subject><ispartof>Computer aided design, 2004-02, Vol.36 (2), p.123-140</ispartof><rights>2004 Elsevier Ltd</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c416t-4fda2e5ec20ea43077ebcbf4b96790ae7ecf1b1f32c55db9f1b939d898f743e63</citedby><cites>FETCH-LOGICAL-c416t-4fda2e5ec20ea43077ebcbf4b96790ae7ecf1b1f32c55db9f1b939d898f743e63</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27924,27925</link.rule.ids></links><search><creatorcontrib>Joan-Arinyo, R.</creatorcontrib><creatorcontrib>Soto-Riera, A.</creatorcontrib><creatorcontrib>Vila-Marta, S.</creatorcontrib><creatorcontrib>Vilaplana-Pastó, J.</creatorcontrib><title>Revisiting decomposition analysis of geometric constraint graphs</title><title>Computer aided design</title><description>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.</description><subject>Constraint solving</subject><subject>Geometric constraints</subject><subject>Graph-based constraint solving</subject><issn>0010-4485</issn><issn>1879-2685</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2004</creationdate><recordtype>article</recordtype><recordid>eNqNkEtLxDAUhYMoOI7-BKEr0UU1z6ZZqQy-YEDwsQ5pejNG2qYmnYH593ZmxK2uLge-c-B-CJ0SfEkwKa5eMSY457wU55hdYIyFzMUempBSqpwWpdhHk1_kEB2l9DlClDA1QTcvsPLJD75bZDXY0PZhk0KXmc406-RTFly2gNDCEL3NbOjSEI3vhmwRTf-RjtGBM02Ck587Re_3d2-zx3z-_PA0u53nlpNiyLmrDQUBlmIwnGEpobKV45UqpMIGJFhHKuIYtULUlRqDYqouVekkZ1CwKTrb7fYxfC0hDbr1yULTmA7CMmlaSkGFov8AGZcl5SModqCNIaUITvfRtyauNcF6I1ZvxeqNNY2Z3orVYuxd73owvrvyEHWyHjoLtY9gB10H_8fCN-rjgSI</recordid><startdate>20040201</startdate><enddate>20040201</enddate><creator>Joan-Arinyo, R.</creator><creator>Soto-Riera, A.</creator><creator>Vila-Marta, S.</creator><creator>Vilaplana-Pastó, J.</creator><general>Elsevier Ltd</general><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>8FD</scope><scope>F28</scope><scope>FR3</scope><scope>H8D</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>20040201</creationdate><title>Revisiting decomposition analysis of geometric constraint graphs</title><author>Joan-Arinyo, R. ; Soto-Riera, A. ; Vila-Marta, S. ; Vilaplana-Pastó, J.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c416t-4fda2e5ec20ea43077ebcbf4b96790ae7ecf1b1f32c55db9f1b939d898f743e63</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2004</creationdate><topic>Constraint solving</topic><topic>Geometric constraints</topic><topic>Graph-based constraint solving</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Joan-Arinyo, R.</creatorcontrib><creatorcontrib>Soto-Riera, A.</creatorcontrib><creatorcontrib>Vila-Marta, S.</creatorcontrib><creatorcontrib>Vilaplana-Pastó, J.</creatorcontrib><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ANTE: Abstracts in New Technology &amp; Engineering</collection><collection>Engineering Research Database</collection><collection>Aerospace Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>Computer aided design</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Joan-Arinyo, R.</au><au>Soto-Riera, A.</au><au>Vila-Marta, S.</au><au>Vilaplana-Pastó, J.</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Revisiting decomposition analysis of geometric constraint graphs</atitle><jtitle>Computer aided design</jtitle><date>2004-02-01</date><risdate>2004</risdate><volume>36</volume><issue>2</issue><spage>123</spage><epage>140</epage><pages>123-140</pages><issn>0010-4485</issn><eissn>1879-2685</eissn><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 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.</abstract><pub>Elsevier Ltd</pub><doi>10.1016/S0010-4485(03)00057-5</doi><tpages>18</tpages><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 0010-4485
ispartof Computer aided design, 2004-02, Vol.36 (2), p.123-140
issn 0010-4485
1879-2685
language eng
recordid cdi_proquest_miscellaneous_28752592
source ScienceDirect Journals
subjects Constraint solving
Geometric constraints
Graph-based constraint solving
title Revisiting decomposition analysis of geometric constraint graphs
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-01T16%3A46%3A35IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Revisiting%20decomposition%20analysis%20of%20geometric%20constraint%20graphs&rft.jtitle=Computer%20aided%20design&rft.au=Joan-Arinyo,%20R.&rft.date=2004-02-01&rft.volume=36&rft.issue=2&rft.spage=123&rft.epage=140&rft.pages=123-140&rft.issn=0010-4485&rft.eissn=1879-2685&rft_id=info:doi/10.1016/S0010-4485(03)00057-5&rft_dat=%3Cproquest_cross%3E28347824%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c416t-4fda2e5ec20ea43077ebcbf4b96790ae7ecf1b1f32c55db9f1b939d898f743e63%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=28347824&rft_id=info:pmid/&rfr_iscdi=true