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

本研究利用Groebner基方法的新成果和技术，设计出一种高效可靠的算法来寻找几何对象的隐式表示。寻找隐式表示的过程也被称为隐式化，它在计算机辅助几何设计（CAGD），可视化和实体建模等领域有应用。该方法是利用一种新的隐式化方法，这是可靠和有效的。可靠的方法是一种理论上永远不会给出正确答案的方法。高效的方法是具有更好的复杂度或更合理的运行时间并且消耗更少内存的方法。一个高效可靠的隐式化算法将为曲线曲面设计中的分析提供方便。例如，它可以用于寻找表面的交点，以验证是否一个点位于表面上，从这个研究项目的软件产品正在分发给有兴趣使用新成果的研究人员。调查使用一个确定性的Groebner行走方法转换成其隐式形式的表面的参数表示。对于有理参数曲面，作者使用不同的方法来处理基点，因为不再需要计算起始圆锥的Groebner基。这种方法提高了算法的效率，因为通常消耗大量时间和存储空间的隐式表示的计算被替换为沿着行走路径沿着的一系列小计算，然后使用线性变换提升结果。第二个任务是减少中间多项式的项的数量，并找到用于检测不必要的减少的标准。实验结果表明，确定性Groebner行走转换方法的隐式化的大部分时间用于减少提升后的最小基，但这需要许多不必要的计算。这种方法只检测必要的减少，从而大大提高了算法的效率，并显着减少了内存空间。

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.