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

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.


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
Full Text: DOI


[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)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.