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

SGER：用于查找几何对象隐式表示的高效 Groebner 基础计算

• 批准号: 0333746
• 负责人: Quoc-Nam Tran
• 金额: $ 7.59万
• 依托单位: Lamar University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-09-15 至 2005-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0333746&HistoricalAwards=false
• 关键词: SGER; Efficient; Groebner; Basis; Computation

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.

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