### 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 language | English (US) |
---|---|

Title of host publication | Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC 1994 |

Publisher | Association for Computing Machinery |

Pages | 224-233 |

Number of pages | 10 |

ISBN (Electronic) | 0897916387 |

DOIs | |

State | Published - Aug 1 1994 |

Event | 1994 International Symposium on Symbolic and Algebraic Computation, ISSAC 1994 - Oxford, United Kingdom Duration: Jul 20 1994 → Jul 22 1994 |

### Publication series

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

Volume | Part F129423 |

### Other

Other | 1994 International Symposium on Symbolic and Algebraic Computation, ISSAC 1994 |
---|---|

Country | United Kingdom |

City | Oxford |

Period | 7/20/94 → 7/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

*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