Geometric constraint subsets and subgraphs in the analysis of assemblies and mechanisms

Geometric Reasoning ability is central to many applications in CAD/CAM/CAPP environments -- An increasing demand exists for Geometric Reasoning systems which evaluate the feasibility of virtual scenes specified by geometric relations -- Thus, the Geometric Constraint Satisfaction or Scene Feasibilit...

Full description

Autores:
Ruíz, Óscar E.
Ferreira, Placid M.
Tipo de recurso:
Fecha de publicación:
2006
Institución:
Universidad EAFIT
Repositorio:
Repositorio EAFIT
Idioma:
eng
OAI Identifier:
oai:repository.eafit.edu.co:10784/9691
Acceso en línea:
http://hdl.handle.net/10784/9691
Palabra clave:
POLINOMIOS
GEOMETRÍA ALGEBRÁICA
ALGORITMOS (COMPUTADORES)
ÁLGEBRA CONMUTATIVA
Geometry, algebraic
Polynomials
Computer algorithms
Commutative algebra
Geometry
algebraic
Polynomials
Computer algorithms
Commutative algebra
Restricciones geométricas
Sistemas CAD/CAM
Bases de Gröbner
Rights
License
Acceso abierto
id REPOEAFIT2_4b977faea8642b96d9ce489076836eca
oai_identifier_str oai:repository.eafit.edu.co:10784/9691
network_acronym_str REPOEAFIT2
network_name_str Repositorio EAFIT
repository_id_str
dc.title.eng.fl_str_mv Geometric constraint subsets and subgraphs in the analysis of assemblies and mechanisms
title Geometric constraint subsets and subgraphs in the analysis of assemblies and mechanisms
spellingShingle Geometric constraint subsets and subgraphs in the analysis of assemblies and mechanisms
POLINOMIOS
GEOMETRÍA ALGEBRÁICA
ALGORITMOS (COMPUTADORES)
ÁLGEBRA CONMUTATIVA
Geometry, algebraic
Polynomials
Computer algorithms
Commutative algebra
Geometry
algebraic
Polynomials
Computer algorithms
Commutative algebra
Restricciones geométricas
Sistemas CAD/CAM
Bases de Gröbner
title_short Geometric constraint subsets and subgraphs in the analysis of assemblies and mechanisms
title_full Geometric constraint subsets and subgraphs in the analysis of assemblies and mechanisms
title_fullStr Geometric constraint subsets and subgraphs in the analysis of assemblies and mechanisms
title_full_unstemmed Geometric constraint subsets and subgraphs in the analysis of assemblies and mechanisms
title_sort Geometric constraint subsets and subgraphs in the analysis of assemblies and mechanisms
dc.creator.fl_str_mv Ruíz, Óscar E.
Ferreira, Placid M.
dc.contributor.department.spa.fl_str_mv Universidad EAFIT. Departamento de Ingeniería Mecánica
dc.contributor.author.none.fl_str_mv Ruíz, Óscar E.
Ferreira, Placid M.
dc.contributor.researchgroup.spa.fl_str_mv Laboratorio CAD/CAM/CAE
dc.subject.lemb.spa.fl_str_mv POLINOMIOS
GEOMETRÍA ALGEBRÁICA
ALGORITMOS (COMPUTADORES)
ÁLGEBRA CONMUTATIVA
topic POLINOMIOS
GEOMETRÍA ALGEBRÁICA
ALGORITMOS (COMPUTADORES)
ÁLGEBRA CONMUTATIVA
Geometry, algebraic
Polynomials
Computer algorithms
Commutative algebra
Geometry
algebraic
Polynomials
Computer algorithms
Commutative algebra
Restricciones geométricas
Sistemas CAD/CAM
Bases de Gröbner
dc.subject.keyword.spa.fl_str_mv Geometry, algebraic
Polynomials
Computer algorithms
Commutative algebra
dc.subject.keyword.eng.fl_str_mv Geometry
algebraic
Polynomials
Computer algorithms
Commutative algebra
dc.subject.keyword..keywor.fl_str_mv Restricciones geométricas
Sistemas CAD/CAM
Bases de Gröbner
description Geometric Reasoning ability is central to many applications in CAD/CAM/CAPP environments -- An increasing demand exists for Geometric Reasoning systems which evaluate the feasibility of virtual scenes specified by geometric relations -- Thus, the Geometric Constraint Satisfaction or Scene Feasibility (GCS/SF) problem consists of a basic scenario containing geometric entities, whose context is used to propose constraining relations among still undefined entities -- If the constraint specification is consistent, the answer of the problem is one of finitely or infinitely many solution scenarios satisfying the prescribed constraints -- Otherwise, a diagnostic of inconsistency is expected -- The three main approaches used for this problem are numerical, procedural or operational and mathematical -- Numerical and procedural approaches answer only part of the problem, and are not complete in the sense that a failure to provide an answer does not preclude the existence of one -- The mathematical approach previously presented by the authors describes the problem using a set of polynomial equations -- The common roots to this set of polynomials characterizes the solution space for such a problem -- That work presents the use of Groebner basis techniques for verifying the consistency of the constraints -- It also integrates subgroups of the Special Euclidean Group of Displacements SE(3) in the problem formulation to exploit the structure implied by geometric relations -- Although theoretically sound, these techniques require large amounts of computing resources -- This work proposes Divide-and-Conquer techniques applied to local GCS/SF subproblems to identify strongly constrained clusters of geometric entities -- The identification and preprocessing of these clusters generally reduces the effort required in solving the overall problem -- Cluster identification can be related to identifying short cycles in the Spatial Con straint graph for the GCS/SF problem -- Their preprocessing uses the aforementioned Algebraic Geometry and Group theoretical techniques on the local GCS/SF problems that correspond to these cycles -- Besides improving theefficiency of the solution approach, the Divide-and-Conquer techniques capture the physical essence of the problem -- This is illustrated by applying the discussed techniques to the analysis of the degrees of freedom of mechanisms
publishDate 2006
dc.date.issued.none.fl_str_mv 2006-03
dc.date.available.none.fl_str_mv 2016-11-18T22:25:09Z
dc.date.accessioned.none.fl_str_mv 2016-11-18T22:25:09Z
dc.type.eng.fl_str_mv info:eu-repo/semantics/article
article
info:eu-repo/semantics/publishedVersion
publishedVersion
dc.type.coarversion.fl_str_mv http://purl.org/coar/version/c_970fb48d4fbd8a85
dc.type.coar.fl_str_mv http://purl.org/coar/resource_type/c_6501
http://purl.org/coar/resource_type/c_2df8fbb1
dc.type.local.spa.fl_str_mv Artículo
status_str publishedVersion
dc.identifier.issn.none.fl_str_mv 1794-9165
dc.identifier.uri.none.fl_str_mv http://hdl.handle.net/10784/9691
identifier_str_mv 1794-9165
url http://hdl.handle.net/10784/9691
dc.language.iso.eng.fl_str_mv eng
language eng
dc.relation.ispartof.spa.fl_str_mv Ingeniería y Ciencia, Volume 2, Issue 3, pp. 103-137
dc.relation.uri.none.fl_str_mv http://publicaciones.eafit.edu.co/index.php/ingciencia/article/view/489
dc.rights.coar.fl_str_mv http://purl.org/coar/access_right/c_abf2
dc.rights.local.spa.fl_str_mv Acceso abierto
rights_invalid_str_mv Acceso abierto
http://purl.org/coar/access_right/c_abf2
dc.format.eng.fl_str_mv application/pdf
dc.publisher.spa.fl_str_mv Universidad EAFIT
institution Universidad EAFIT
bitstream.url.fl_str_mv https://repository.eafit.edu.co/bitstreams/9bcdf9ee-1e93-4a3f-aa3e-7a5c609af7d3/download
https://repository.eafit.edu.co/bitstreams/7e32e7a1-c31e-4f77-811f-a2eddfb88fb7/download
bitstream.checksum.fl_str_mv 76025f86b095439b7ac65b367055d40c
2bdc2ed0672987fdfa6ff0c759f4bd29
bitstream.checksumAlgorithm.fl_str_mv MD5
MD5
repository.name.fl_str_mv Repositorio Institucional Universidad EAFIT
repository.mail.fl_str_mv repositorio@eafit.edu.co
_version_ 1814110190178402304
spelling 2016-11-18T22:25:09Z2006-032016-11-18T22:25:09Z1794-9165http://hdl.handle.net/10784/9691Geometric Reasoning ability is central to many applications in CAD/CAM/CAPP environments -- An increasing demand exists for Geometric Reasoning systems which evaluate the feasibility of virtual scenes specified by geometric relations -- Thus, the Geometric Constraint Satisfaction or Scene Feasibility (GCS/SF) problem consists of a basic scenario containing geometric entities, whose context is used to propose constraining relations among still undefined entities -- If the constraint specification is consistent, the answer of the problem is one of finitely or infinitely many solution scenarios satisfying the prescribed constraints -- Otherwise, a diagnostic of inconsistency is expected -- The three main approaches used for this problem are numerical, procedural or operational and mathematical -- Numerical and procedural approaches answer only part of the problem, and are not complete in the sense that a failure to provide an answer does not preclude the existence of one -- The mathematical approach previously presented by the authors describes the problem using a set of polynomial equations -- The common roots to this set of polynomials characterizes the solution space for such a problem -- That work presents the use of Groebner basis techniques for verifying the consistency of the constraints -- It also integrates subgroups of the Special Euclidean Group of Displacements SE(3) in the problem formulation to exploit the structure implied by geometric relations -- Although theoretically sound, these techniques require large amounts of computing resources -- This work proposes Divide-and-Conquer techniques applied to local GCS/SF subproblems to identify strongly constrained clusters of geometric entities -- The identification and preprocessing of these clusters generally reduces the effort required in solving the overall problem -- Cluster identification can be related to identifying short cycles in the Spatial Con straint graph for the GCS/SF problem -- Their preprocessing uses the aforementioned Algebraic Geometry and Group theoretical techniques on the local GCS/SF problems that correspond to these cycles -- Besides improving theefficiency of the solution approach, the Divide-and-Conquer techniques capture the physical essence of the problem -- This is illustrated by applying the discussed techniques to the analysis of the degrees of freedom of mechanismsapplication/pdfengUniversidad EAFITIngeniería y Ciencia, Volume 2, Issue 3, pp. 103-137http://publicaciones.eafit.edu.co/index.php/ingciencia/article/view/489Acceso abiertohttp://purl.org/coar/access_right/c_abf2Geometric constraint subsets and subgraphs in the analysis of assemblies and mechanismsinfo:eu-repo/semantics/articlearticleinfo:eu-repo/semantics/publishedVersionpublishedVersionArtículohttp://purl.org/coar/version/c_970fb48d4fbd8a85http://purl.org/coar/resource_type/c_6501http://purl.org/coar/resource_type/c_2df8fbb1POLINOMIOSGEOMETRÍA ALGEBRÁICAALGORITMOS (COMPUTADORES)ÁLGEBRA CONMUTATIVAGeometry, algebraicPolynomialsComputer algorithmsCommutative algebraGeometryalgebraicPolynomialsComputer algorithmsCommutative algebraRestricciones geométricasSistemas CAD/CAMBases de GröbnerUniversidad EAFIT. Departamento de Ingeniería MecánicaRuíz, Óscar E.Ferreira, Placid M.Laboratorio CAD/CAM/CAEIngeniería y CienciaIngeniería y Ciencia23103137LICENSElicense.txtlicense.txttext/plain; charset=utf-82556https://repository.eafit.edu.co/bitstreams/9bcdf9ee-1e93-4a3f-aa3e-7a5c609af7d3/download76025f86b095439b7ac65b367055d40cMD51ORIGINALgeometricConstraintSubsetsandSubgraphsintheAnalisys.pdfgeometricConstraintSubsetsandSubgraphsintheAnalisys.pdfapplication/pdf321555https://repository.eafit.edu.co/bitstreams/7e32e7a1-c31e-4f77-811f-a2eddfb88fb7/download2bdc2ed0672987fdfa6ff0c759f4bd29MD5210784/9691oai:repository.eafit.edu.co:10784/96912021-09-03 15:43:55.803open.accesshttps://repository.eafit.edu.coRepositorio Institucional Universidad EAFITrepositorio@eafit.edu.coSS4gT0JSQVMgWUEgUFVCTElDQURBUwoKUGFyYSBvYnJhcyB5YSBwdWJsaWNhZGFzIHNlIHJlcXVpZXJlLCBwYXJhIGVsIGFyY2hpdm8geSBkaXZ1bGdhY2nDs24gZW4gZWwgUmVwb3NpdG9yaW8gSW5zdGl0dWNpb25hbCBkZSBsYSBVbml2ZXJzaWRhZCBFQUZJVCwgcXVlIGVsIGF1dG9yIGNvbm96Y2EgeSB2YWxpZGUgbGFzIGNvbmRpY2lvbmVzIGVuIHF1ZSBoYSBzdXNjcml0byBsb3MgYWN1ZXJkb3MgZGUgY2VzacOzbiBvIGxpY2VuY2lhIGRlIGRlcmVjaG9zIGRlIGF1dG9yIGNvbiBsYShzKSBlZGl0b3JpYWwoZXMpIGVuIGxhcyBxdWUgaGEgcHVibGljYWRvIGxhIG9icmEuCgpFc3RhIHZlcmlmaWNhY2nDs24gc2UgcHVlZGUgcmVhbGl6YXIgY29uc3VsdGFuZG8gbGFzIGJhc2VzIGRlIGRhdG9zIFNIRVJQQSAvIFJPTUVPIHkgRFVMQ0lORUEsIHBhcmEgY29ub2NlciBsYSBwb2zDrXRpY2Egc29icmUgZGVyZWNob3MgZGUgYXV0b3IgZGUgbGEgcmVzcGVjdGl2YSBlZGl0b3JpYWwuIEVuIGNhc28gZGUgcXVlIGxhIGVkaXRvcmlhbCBubyBzZSBlbmN1ZW50cmUgZW4gZXN0YXMgYmFzZXMgZGUgZGF0b3MsIGVsIGF1dG9yIGRlYmUgY29uc3VsdGFyIGRpcmVjdGFtZW50ZSBjb24gZWwgcmVzcG9uc2FibGUgZGUgbGEgZmlybWEgZGUgbGEgbGljZW5jaWEgcG9yIHBhcnRlIGRlIGxhIGVkaXRvcmlhbC4KCkNvbnN1bHRhciBQb2zDrXRpY2EgZGVsIFJlcG9zaXRvcmlvIEluc3RpdHVjaW9uYWwuCgpJSS4gT0JSQVMgSU7DiURJVEFTCgpFbCBhdXRvciBjb25zZXJ2YSB0b2RvcyBsb3MgZGVyZWNob3MsIGNvbiBsbyBjdWFsIHB1ZWRlIHB1YmxpY2FybGEgcG9zdGVyaW9ybWVudGUuIFNlIHJlY29taWVuZGEgY29ub2Nlci9yZXZpc2FyIGxhIHBvbMOtdGljYSBkZSBkb25kZSBzZSBwcmV2w6kgcHVibGljYXIsIGRhZG8gcXVlIGFsZ3Vub3MgcHVibGljYWRvcmVzIHPDs2xvIGFjZXB0YW4gdHJhYmFqb3Mgbm8gZGlmdW5kaWRvcyBjb24gYW50ZXJpb3JpZGFkLiBQdWVkZSBjb25zdWx0YXIgbGEgYmFzZSBkZSBkYXRvcyBTSEVSUEEvUk9NRU8qIG8gRFVMQ0lORUEqKiwgcGFyYSBjb25vY2VyIGxhIHBvbMOtdGljYSBzb2JyZSBkZXJlY2hvcyBkZSBhdXRvciBkZSBsYSByZXNwZWN0aXZhIGVkaXRvcmlhbC4KCkFVVE9SSVpBQ0nDk04gREUgUFVCTElDQUNJw5NOIEVOIEZPUk1BIEFOQUzDk0dJQ0EgTyBESUdJVEFMIERFIExBIE9CUkEuCgpBdXRvcml6byBlbiBmb3JtYSBncmF0dWl0YSB5IHBvciB0aWVtcG8gaW5kZWZpbmlkbyBhIGxhIFVuaXZlcnNpZGFkIEVBRklUIHBhcmEgcmVhbGl6YXIgbGFzIHNpZ3VpZW50ZXMgYWN0aXZpZGFkZXM6CgotIFB1YmxpY2FyIGVuIGZvcm1hIGVsZWN0csOzbmljYSBvIGRpdnVsZ2FyIHBvciBtZWRpbyBlbGVjdHLDs25pY28gZWwgdGV4dG8gZGVsIHRyYWJham8gY29uIGVsIGZpbiBkZSBzZXIgY29uc3VsdGFkbyBwb3IgZWwgcMO6YmxpY28gZW4gaHR0cDovL3d3dy5lYWZpdC5lZHUuY28vYmlibGlvdGVjYQotIFB1YmxpY2FyIGVuIGZvcm1hIGVsZWN0csOzbmljYSwgZGl2dWxnYXIgcG9yIG1lZGlvIGVsZWN0csOzbmljbyB5IHByZXNlcnZhciBlbCB0ZXh0byBkZWwgdHJhYmFqbyBjb24gZWwgZmluIGRlIHNlciBjb25zdWx0YWRvIHBvciBlbCBww7pibGljbyBlbiBodHRwOi8vcmVwb3NpdG9yeS5lYWZpdC5lZHUuY28KClRvZG8gcGVyc29uYSBxdWUgY29uc3VsdGUgZWwgbWF0ZXJpYWwgYmllbiBzZWEgZGUgZm9ybWEgYW5hbMOzZ2ljYSBvIGRpZ2l0YWwsIHBvZHLDoSByZWFsaXphciBjaXRhcyBjb25mb3JtZSBhIGxvIHBlcm1pdGlkbyBwb3IgbGEgbGV5IGNpdGFuZG8gZW4gdG9kbyBjYXNvIGxhcyBmdWVudGVzLiBFc3RhIGF1dG9yaXphY2nDs24gbm8gaW1wbGljYSByZW51bmNpYSBhIGxhIGZhY3VsdGFkIHF1ZSB0ZW5nbyBkZSBwdWJsaWNhciB0b3RhbCBvIHBhcmNpYWxtZW50ZSBsYSBvYnJhLgoKRGVjbGFybyBxdWUgc295IGVsIGF1dG9yIHkgdGl0dWxhciBkZSBsb3MgZGVyZWNob3MgZGUgYXV0b3Igc29icmUgbGEgb2JyYSwgeSBxdWUgbGEgbWlzbWEgZXMgb3JpZ2luYWwsIHBvciBsbyB0YW50byBsYSBVbml2ZXJzaWRhZCBFQUZJVCBubyBzZXLDoSByZXNwb25zYWJsZSBkZSBuaW5ndW5hIHJlY2xhbWFjacOzbiBxdWUgcHVkaWVyYSBzdXJnaXIgcG9yIHBhcnRlIGRlIHRlcmNlcm9zIHF1ZSBpbnZvcXVlbiBhdXRvcsOtYSBkZSBsYSBvYnJhIHF1ZSBwcmVzZW50by4KClNpIHRpZW5lIGFsZ3VuYSBkdWRhIHNvYnJlIGxhIGxpY2VuY2lhLCBwb3IgZmF2b3IsIGNvbnRhY3RlIGNvbiBlbCBhZG1pbmlzdHJhZG9yIGRlbCBzaXN0ZW1hLgoKRGVjbGFybyBxdWUgY29ub3pjbyBsYSBwb2zDrXRpY2EgZGVsIFJlcG9zaXRvcmlvIEluc3RpdHVjaW9uYWwgeSBjb25jZWRvIGxhIGF1dG9yaXphY2nDs24uCgpfX19fX19fX19fX19fX18KKCopIFNoZXJwYS4gRGlzcG9uaWJsZSBlbjogaHR0cDovL3d3dy5zaGVycGEuYWMudWsvcm9tZW8vP2xhPWVzCigqKikgRHVsY2luZWEuIERpc3BvbmlibGUgZW46IGh0dHA6Ly93d3cuYWNjZXNvYWJpZXJ0by5uZXQvZHVsY2luZWEK