UTILIZING MOMENT INVARIANTS AND GROBNER BASES TO REASON ABOUT SHAPES

Shapes such as triangles or rectangles can be defined in terms of gel, metric properties invariant under a group of transformations. Complex shapes can be described by logic formulas with simpler shapes as the a toms. A standard technique for computing invariant properties of simpl e shapes is the method of moment invariants, known since the early 196 0s. We generalize this technique to shapes described by arbitrary mono tone formulas (formulas in propositional logic without negation). Our technique produces a reduced Grobner basis for approximate shape descr iptions. We show how to use this representation to solve decision prob lems related to shapes. Examples include determining if a figure has a particular shape, if one description of a shape is more general than another, and whether a specific geometric property is really necessary for specifying a shape. Unlike geometry theorem proving, our approach does not require the shapes to be explicitly defined. Instead, logic formulas combined with measurements performed on actual shape instance s are used to compute well-characterized least squares approximations to the shapes. Our results provide a proof that decision problems stat ed in terms of these approximations can be solved in a finite number o f steps.