Intersection points algorithm for piecewise algebraic curves based on Groebner bases. (English) Zbl 1176.65019

Lang, Feng-Gong; Wang, Ren-Hong

J. Appl. Math. Comput. 29, No. 1-2, 357-366 (2009).

Summary: A piecewise algebraic curve is defined as the zero set of a bivariate spline. In this paper, we mainly study the intersection points algorithm for two given piecewise algebraic curves based on Groebner bases. Given a domain \(D\) and a partition \(\Delta \), we present a flow and introduce the truncated signs, and then represent the two piecewise algebraic curves in the global form. We get their Groebner bases with respect to a lexicographic order and adopt the interval arithmetic in the back-substitution process, which makes the algorithm numerically precise. An example is also presented to show the algorithm’s feasibility and effectiveness.

MSC:

65D18	Numerical aspects of computer graphics, image analysis, and computational geometry
65D07	Numerical computation using splines
14Q05	Computational aspects of algebraic curves
68W25	Approximation algorithms
13P10	Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
65G30	Interval and finite arithmetic

Keywords:

piecewise algebraic curve; multivariate spline; truncated sign; Gröbner bases; interval arithmetic; numerical example; intersection points algorithm

References:

[1]	Wang, R.H.: The structure characterization and interpolation for multivariate splines. Acta Math. Sin. 18, 91–106 (1975). English transl., 18, 10–39 (1975) · Zbl 0358.41004
[2]	Wang, R.H.: Multivariate Spline Functions and Their Applications. Science Press/Kluwer, Beijing/New York/London/Boston (1994/2001)
[3]	Wang, R.H.: Recent researches on multivariate spline and piecewise algebraic variety. J. Comput. Appl. Math. (2007). doi: 10.1016/j.cam.2007.10.056
[4]	Walker, R.J.: Algebraic Curves. Dover, New York (1950) · Zbl 0039.37701
[5]	Hartshorne, R.: Algebraic Geometry. Springer, New York (1977) · Zbl 0367.14001
[6]	Shi, X.Q., Wang, R.H.: Bezout number for piecewise algebraic curves. BIT 39(1), 339–349 (1999) · Zbl 0933.65017
[7]	Wang, R.H., Xu, Z.Q.: The estimate of Bezout number for piecewise algebraic curves. Sci. China (Ser. A) 33(2), 185–192 (2003)
[8]	Wang, R.H., Zhu, C.G.: Nöther-type theorem of piecewise algebraic curves. Prog. Nat. Sci. 14(4), 309–313 (2004) · Zbl 1083.14525
[9]	Wang, R.H., Zhu, C.G.: Cayley-Bacharach theorem of piecewise algebraic curves. J. Comput. Appl. Math. 163, 269–276 (2004) · Zbl 1070.14034
[10]	Itenberg, I., Viro, O.: Patchworking algebraic curves disproves the Ragsdale conjecture. Math. Intell. 1, 19–28 (1996) · Zbl 0876.14017
[11]	Xu, Z.Q.: Multivariate splines, piecewise algebraic curves and linear diophantine equations. Ph.D. thesis, Dalian University of Technology, China (2003)
[12]	Cox, D., Little, J., O’shea, D.: Ideals, Varieties, and Algorithms, 2nd edn. Springer, New York (1996)
[13]	Becker, T., Weispfenning, V.: Groebner Bases. Springer, New York (1993) · Zbl 0772.13010
[14]	Cox, D., Little, J., O’shea, D.: Using Algebraic Geometry. Springer, New York (1997)
[15]	Boege, W., Gebauer, R., Kredel, H.: Some examples for solving systems of algebraic equations by calculating Groebner bases. J. Symb. Comput. 2, 83–98 (1986) · Zbl 0602.65032
[16]	Moore, R.E.: Interval Analysis. Prentice-Hall, Englewood Cliffs (1966) · Zbl 0176.13301
[17]	Moore, R.E., Bierbaum, F.: Methods and Applications of Interval Analysis. SIAM, Philadelphia (1979)
[18]	Munack, H.: On global optimization using interval arithmetic. Computing 48(3–4), 319–336 (1992) · Zbl 0774.65036
[19]	Snyder, J.M.: Interval analysis for computer graphics. ACM SIGGRAPH Comput. Graph. 26(2), 121–130 (1992)
[20]	Moore, R., Lodwick, W.: Interval analysis and fuzzy set theory. Fuzzy Sets Syst. 135(1), 5–9 (2003) · Zbl 1015.03513
[21]	Chen, F.L., Yang, W.: The application of interval arithmetic in Wu-method for solving algebraic equations system. Sci. China (Ser. A) 35(8), 910–921 (2005)