TY - GEN

T1 - Algebraic geometry and group theory in geometric constraint satisfaction

AU - Ruiz, Oscar E.S.

AU - Ferreira, Placid M.

N1 - Publisher Copyright:
© 1994 ACM.

PY - 1994/8/1

Y1 - 1994/8/1

N2 - The determination of a set of geometric entities that satisfy a series of geometric relations (constraints) constitutes the Geometric Constraint Satisfaction or Scene Feasibility (GCS/SF) problem. This problem appears in different forms in Assembly Planning, Constraint Driven Design, Computer Vision, etc. Its solution is related to the existence of roots to systems of polynomial equations. Previous attempts using exclusively numerical (geometry) or symbolic (topology) solutions for this problem present shortcomings regarding characterization of solution space, incapability to deal with geometric and topological inconsistencies, and very high computational expenses. In this investigation Grobner Bases are used for the characterization of the algebraic variety of the ideal generated by the set of polynomials. Properties of Grobner Bases provide a theoretical framework responding to questions about consistency, ambiguity, and dimension of the solution space. It also allows for the integration of geometric and topological reasoning. The high computational cost of Buchberger's algorithm for the Grobner Basis is compensated by the choice of a non redundant set of variables, determined by the characterization of constraints based on the subgroups of the group of Euclidean displacements SE(3). Examples have shown the advantage of using group based variables. One of those examples is discussed.

AB - The determination of a set of geometric entities that satisfy a series of geometric relations (constraints) constitutes the Geometric Constraint Satisfaction or Scene Feasibility (GCS/SF) problem. This problem appears in different forms in Assembly Planning, Constraint Driven Design, Computer Vision, etc. Its solution is related to the existence of roots to systems of polynomial equations. Previous attempts using exclusively numerical (geometry) or symbolic (topology) solutions for this problem present shortcomings regarding characterization of solution space, incapability to deal with geometric and topological inconsistencies, and very high computational expenses. In this investigation Grobner Bases are used for the characterization of the algebraic variety of the ideal generated by the set of polynomials. Properties of Grobner Bases provide a theoretical framework responding to questions about consistency, ambiguity, and dimension of the solution space. It also allows for the integration of geometric and topological reasoning. The high computational cost of Buchberger's algorithm for the Grobner Basis is compensated by the choice of a non redundant set of variables, determined by the characterization of constraints based on the subgroups of the group of Euclidean displacements SE(3). Examples have shown the advantage of using group based variables. One of those examples is discussed.

UR - http://www.scopus.com/inward/record.url?scp=81755166747&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=81755166747&partnerID=8YFLogxK

U2 - 10.1145/190347.190421

DO - 10.1145/190347.190421

M3 - Conference contribution

AN - SCOPUS:81755166747

T3 - Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC

SP - 224

EP - 233

BT - Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC 1994

PB - Association for Computing Machinery

T2 - 1994 International Symposium on Symbolic and Algebraic Computation, ISSAC 1994

Y2 - 20 July 1994 through 22 July 1994

ER -