SGER: Efficient Groebner Basis Computation for Finding Implicit Representations of Geometric Objects

Lamar University, Beaumont TX

Investigators

Abstract

This research uses new results and techniques from the method of Groebner bases to devise an efficient and reliable algorithm for finding implicit representations of geometric objects. The process of finding implicit representations is also known as implicitization, which has applications in areas such as computer aided geometric design (CAGD), visualization and solid modeling. The approach is to utilize a novel method for implicitization that is both reliable and efficient. A reliable method is a method that theoretically never fails to give a correct answer. An efficient method is a method that has a better complexity or a more reasonable running time and consumes less memory. An efficient and reliable implicitization algorithm will facilitate the analysis needed in the design of curves and surfaces. For example, it can be used for finding the intersection of surfaces, to verify whether or not a point lies on a surface, etc. Software products from this research project are being distributed to researchers who are interested in using the new results. The investigation uses a deterministic Groebner walk method to convert a parametric representation of a surface into its implicit form. For rational parametric surfaces, the author uses a different approach to deal with base points in that the calculation of a Groebner basis for the starting cone is no longer needed. This approach improves the efficiency of algorithms because the usual calculation of the implicit representation, which often consumes a lot of time and memory space, is replaced by a sequence of small calculations along the walking path and then lift the results using linear transformations. A second task is to reduce the number of terms of the intermediate polynomials and find criteria for detecting unnecessary reduction. Experimental results with the deterministic Groebner walk conversion method show that most of the time for implicitization is used for reducing the minimal bases after lifting, but this entails many unnecessary computations. This approach detects only necessary reductions thus greatly improving the efficiency of algorithms and significantly reducing the memory space.