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.