An Algorithm to Compute the

Abstract

The method of moving surfaces is an effective tool to implicitize rational parametric surfaces, and it has been extensively studied in the past two decades. An essential step in surface implicitization using the method of moving surfaces is to compute a

\mu

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\mu $$\end{document}

-basis of a parametric surface with respect to one variable. The

\mu

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\mu $$\end{document}

-basis is a minimal basis of the syzygy module of a univariate polynomial matrix with special structure defined by the parametric equation of the rational surface. In this paper, we present an efficient algorithm to compute the

\mu

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\mu $$\end{document}

-basis of a parametric surface with respect to a variable based on the special structure of the corresponding univariate polynomial matrix. Analysis on the computational complexity of the algorithm is also provided. Experiments demonstrate that our algorithm is much faster than the general method to compute the

\mu

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\mu $$\end{document}

-bases of arbitrary polynomial matrices and outperforms the

F_5

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$F_5$$\end{document}

algorithm based on Gröbner basis computation for relatively low degree rational surfaces.

Keywords

Rational surface / Implicitization /

\mu

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\mu $$\end{document}

-basis')">

\mu

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\mu $$\end{document}

-basis / Polynomial matrix factorization

References

[1] Botbol N, Dickenstein A. Implicitization of rational hypersurfaces via linear syzygies: a practical overview. J. Symb. Comput., 2016, 74: 493-512,

[2] Busé L, Chen F. Determinantal tensor product surfaces and the method of moving quadrics. Trans. Am. Math. Soc., 2021, 374(7): 4931-4952,

[3] Busé L, Cox DA, D’Andrea C. Implicitization of surfaces in P 3 \documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${ P}^3$$\end{document} in the presence of base points. J. Algebra Appl., 2003, 2(2): 189-214,

[4] Busé, L., Dohm, M.: Implicitization of bihomegenous parametrizations of algebraic surfaces via linear syzygies. In: Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation. pp. 69–76 (2007)

[5] Chen F. Recent advances on surface implicitization. J. Univ. Sci. Technol. China, 2014, 44: 345-361

[6] Chen F, Cox D, Liu Y. The μ \documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\mu $$\end{document}-basis and implicitization of a rational parametric surface. J. Symb. Comput., 2005, 39(6): 689-706,

[7] Chen F, Wang W. The μ \documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\mu $$\end{document}-basis of a planar rational curve properties and computation. Graph Models, 2002, 64(6): 368-381,

[8] Chen F, Zheng J, Sederberg T. The μ \documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\mu $$\end{document}-basis of a rational ruled surface. Comput. Aided Geom. Des., 2001, 18(1): 61-72,

[9] Cox D, Goldman R, Zhang M. On the validity of implicitization by moving quadrics for rational surfaces with no base points. J. Symb. Comput., 2000, 29(3): 419-440,

[10] Cox D, Little J, O’Shea D. . Using Algebraic Geometry, 2005 New York Springer

[11] Cox D, Sederberg T, Chen F. The moving line ideal basis of planar rational curves. Comput. Aided Geom. Des., 1998, 15(8): 803-827,

[12] D’Andrea C. Resultants and moving surfaces. J. Symb. Comput., 2001, 31(5): 585-602,

[13] Deng, J., Chen, F., Shen, L.: Computing μ \documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\mu $$\end{document}-bases of rational curves and surfaces using polynomial matrix factorization. In: Proceedings of the 2005 International Symposium on Symbolic and Algebraic Computation, pp. 132–139 (2005)

[14] Faugère J.C.: A new efficient algorithm for computing Göebner bases without reduction to zero ( F 5 \documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$F_5$$\end{document}). In: Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, pp. 75–83 (2002)

[15] Hong H, Hough Z, Kogan I. Algorithm for computing μ \documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\mu $$\end{document}-bases of univariate polynomials. J. Symb. Comput., 2017, 80: 844-874,

[16] Huang B, Chen F. Computing μ \documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\mu $$\end{document}-bases of univariate polynomial matrices using polynomial matrix factorization. Syst. Sci. Complex, 2021, 34(3): 1189-1206,

[17] Jia X. Role of moving planes and moving spheres following dupin cyclides. Comput. Aided Geom. Des., 2014, 31(3–4): 168-181,

[18] Jia X, Goldman R. μ \documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\mu $$\end{document}-Bases and singularities of rational planar curves. Comput. Aided Geom. Des., 2009, 26(9): 970-988,

[19] Jia X, Goldman R. Using Smith normal forms and μ \documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\mu $$\end{document}-bases to compute all the singularities of rational planar curves. Comput. Aided Geom. Des., 2012, 29(6): 296-314,

[20] Jia X, Shi X, Chen F. Survey on the theory and applications of μ \documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\mu $$\end{document}-bases for rational curves and surfaces. J. Comput. Appl. Math., 2017, 329: 2-23,

[21] Kriezis GA, Prakash PV, Patrikalakis NM. Method for intersecting algebraic surfaces with rational polynomial patches. Comput. Aided Des., 1990, 22(10): 645-654,

[22] Krishnan S, Manocha D. An efficient surface intersection algorithm based on lower-dimensional formulation. ACM Trans. Graph., 1997, 16(1): 74-106,

[23] Lai Y, Chen F. An improved algorithm for constructing moving quadrics from moving planes. J. Syst. Sci. Complex, 2017, 30(6): 1483-1506,

[24] Lai Y, Chen F, Shi X. Implicitizing rational surfaces using moving quadrics constructed from moving planes. J. Symb. Comput., 2016, 77: 127-161,

[25] Lai Y, Chen F, Shi X. Implicitizing rational surfaces without base points by moving planes and moving quadrics. Comput. Aided Geom. Des., 2019, 70: 1-15,

[26] Lai, Y., Chen, F., Shi, X., Gao, Y.: A constructive approach to implicitizing rational surfaces with LCI base points by moving planes and moving quadrics. Comput. Aided Geom. Des. 92(Jan.), 102051 (2022)

[27] Sederberg, T., Chen, F.: Implicitization using moving curves and surfaces. In: Proceedings of SIGGRAPH, pp. 301–308 (1995)

[28] Sederberg T, Saito T, Qi D, Klimaszewski K. Curve implicitization using moving lines. Comput. Aided Geom. Des., 1994, 11(6): 687-706,

[29] Shen L, Goldman R. Implicitizing rational tensor product surfaces using the resultant of three moving planes. ACM Trans. Graph., 2017, 36(5): 1-167,

[30] Song N, Chen F, Goldman R. Axial moving lines and singularities of rational planar curves. Comput. Aided Geom. Des., 2007, 24(4): 200-209,

[31] Song N, Goldman R. μ \documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\mu $$\end{document}-bases for polynomial systems in one variable. Comput. Aided Geom. Des., 2009, 26(2): 217-230,

Funding

National Natural Science Foundation of China(No. 61972368.)