Algebraic geometry and group theory in geometric constraint satisfaction

Oscar E.S. Ruiz, Placid M. Ferreira

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC 1994
PublisherAssociation for Computing Machinery
Pages224-233
Number of pages10
ISBN (Electronic)0897916387
DOIs
StatePublished - Aug 1 1994
Event1994 International Symposium on Symbolic and Algebraic Computation, ISSAC 1994 - Oxford, United Kingdom
Duration: Jul 20 1994Jul 22 1994

Publication series

NameProceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC
VolumePart F129423

Other

Other1994 International Symposium on Symbolic and Algebraic Computation, ISSAC 1994
CountryUnited Kingdom
CityOxford
Period7/20/947/22/94

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Algebraic geometry and group theory in geometric constraint satisfaction'. Together they form a unique fingerprint.

  • Cite this

    Ruiz, O. E. S., & Ferreira, P. M. (1994). Algebraic geometry and group theory in geometric constraint satisfaction. In Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC 1994 (pp. 224-233). (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC; Vol. Part F129423). Association for Computing Machinery. https://doi.org/10.1145/190347.190421