Utilizing Moment Invariants and Gröbner Bases to Reason About Shapes

Abstract

Shapes such as triangles or rectangles can be defined in terms of geometric properties invariant under a group of transformations. Complex shapes can be described by logic formulas with simpler shapes as the atoms. A standard technique for computing invariant properties of simple shapes is the method of moment invariants, known since the early 1960s. We generalize this technique to shapes described by arbitrary monotone formulas (formulas in propositional logic without negation). Our technique produces a reduced Gröbner basisfor approximate shape descriptions. We show how to use this representation to solve decision problems 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 instances are used to compute well‐characterized least squares approximations to the shapes. Our results provide a proof that decision problems stated in terms of these approximations can be solved in a finite number of steps.