样条曲面的区间隐式化、区间曲面的降阶及区间多项式零点的研究
|
摘要
在计算机辅助几何设计中,几何信息的保存至关重要,而由于有些算法的近似性以及计算机浮点误差的存在,很多时候我们只能得到近似的结果。因此,为了保证一些几何处理中的信息不丢失,引进了区间算法的概念,也就是用一个区间来代替一个点来计算。这样就能保证理论上的精确结果包含于计算的结果中,从而避免了信息丢失。
本文的主要研究内容为参数曲面的区间隐式化、区间曲面的降阶以及区间多项式的“零点”问题。我们首先说明了误差控制在计算机辅助几何设计和几何计算中的重要性,并回顾了关于这些问题的研究历史和现状,然后举例说明了引入区间算法的意义。
文中首先讨论了有理B样条曲面的区间隐式化的问题,该问题是曲线情形的推广,对于曲面的相切求交等操作具有很好的应用价值。与曲线情况的先求中心曲线、再通过调整中心曲线得到边界的方法不同,本文采用直接求解区间隐式曲面的两个边界的方法。通过引入影响曲面几何形状的距离、能量、法向等约束建立最优化求解模型,然后给出了该问题的算法以及具体的算例,并讨论了该方法在实际中的应用。
其次讨论区间样条曲面的降阶。区间曲面的降阶克服了减少几何处理复杂度的同时又避免了几何信息丢失的矛盾。本文分别考虑了张量积区间样条曲面的降阶,多边形域上三角剖分区间样条曲面的降阶以及区间PS曲面的降阶。
接着,我们讨论了区间多项式的“零点”问题。我们知道,求解多项式的零点一直是个非常重要的工作,但是由于计算机浮点误差导致了其在实际应用中的一些限制,本文通过引入区间多项式的概念,避免了实际操作中的信息丢失。文中对于单变量情形,给出了“零点”的定义以及“零点”重数的定义,然后给出了多项式的Descartes法则、Budan-Fourier定理以及Sturm定理在区间多项式情形的推广。
最后,我们考虑了两个双变量的区间多项式的“交点”个数问题,对判定两个代数曲线交点个数的Bezout定理进行了推广。
Conservation of geometric information is very important for Computer Aided Geometric Design(CAGD), but only approximate results can be obtained in many cases for the approximation property of some algorithms and the existence of computer float error. Interval operation is presented to avoid information loss during some geometric procedure. Instead of a point, we use an interval that contains the given point in our computation. By this way, the theoretic accurate result is contained in the computation result and the information loss is avoided.
In this paper, our main job is to study interval implicitization of parametric surface, reduction of interval surfaces and the number of "zero" s of an interval polynomial. The importance of error control in CAGD and geometric computation is explained, the history and the state-of-the-art of these problems are reviewed, and then some examples are given to illustrate the significance of interval operation.
First, we study the interval implicitization of rational B-spline surfaces. This problem is the generation of the case of curves which is useful to surface operations, such as seeking the intersection of two tangent surfaces. Instead of the method used in the case of curves in which searching the centric curve is followed by searching the boundary curves, we directly seek the boundary surfaces of the interval implicit surface. By introducing the distance, energy and normal direction of the interval surface that determine the geometric shape, we establish an optimization model and give the algorithm of this problem. We give some examples illustrating the algorithm and discuss the application of this method.
Secondly, we study degree reduction of interval spline surfaces. Degree reduction overcomes the contradiction between reducing the complexity of geometric process and avoiding the geometric information loss. Degree reduction of tensor product interval spline surfaces, triangular partition interval spline surfaces over polygonal domain and interval PS surfaces are respectively discussed.
Thirdly, we study the number of the "zero" s of a univariate interval polynomial. Seeking the roots of polynomials is a very important job, but computer float error restricts its applications. In this thesis, we introduce interval polynomials which avoid the information loss. The definition of "zero" and its multiplicity are presented. Then we generalize Descartes rule, Budan-Fourier theorem and Sturm theorem for polynomials to interval polynomials.
Finally, we study the number of "intersection" s of two multivariate interval polynomials and generalize Bezout theorem which determine the number of the intersections of two algebraic curves.
本文的主要研究内容为参数曲面的区间隐式化、区间曲面的降阶以及区间多项式的“零点”问题。我们首先说明了误差控制在计算机辅助几何设计和几何计算中的重要性,并回顾了关于这些问题的研究历史和现状,然后举例说明了引入区间算法的意义。
文中首先讨论了有理B样条曲面的区间隐式化的问题,该问题是曲线情形的推广,对于曲面的相切求交等操作具有很好的应用价值。与曲线情况的先求中心曲线、再通过调整中心曲线得到边界的方法不同,本文采用直接求解区间隐式曲面的两个边界的方法。通过引入影响曲面几何形状的距离、能量、法向等约束建立最优化求解模型,然后给出了该问题的算法以及具体的算例,并讨论了该方法在实际中的应用。
其次讨论区间样条曲面的降阶。区间曲面的降阶克服了减少几何处理复杂度的同时又避免了几何信息丢失的矛盾。本文分别考虑了张量积区间样条曲面的降阶,多边形域上三角剖分区间样条曲面的降阶以及区间PS曲面的降阶。
接着,我们讨论了区间多项式的“零点”问题。我们知道,求解多项式的零点一直是个非常重要的工作,但是由于计算机浮点误差导致了其在实际应用中的一些限制,本文通过引入区间多项式的概念,避免了实际操作中的信息丢失。文中对于单变量情形,给出了“零点”的定义以及“零点”重数的定义,然后给出了多项式的Descartes法则、Budan-Fourier定理以及Sturm定理在区间多项式情形的推广。
最后,我们考虑了两个双变量的区间多项式的“交点”个数问题,对判定两个代数曲线交点个数的Bezout定理进行了推广。
Conservation of geometric information is very important for Computer Aided Geometric Design(CAGD), but only approximate results can be obtained in many cases for the approximation property of some algorithms and the existence of computer float error. Interval operation is presented to avoid information loss during some geometric procedure. Instead of a point, we use an interval that contains the given point in our computation. By this way, the theoretic accurate result is contained in the computation result and the information loss is avoided.
In this paper, our main job is to study interval implicitization of parametric surface, reduction of interval surfaces and the number of "zero" s of an interval polynomial. The importance of error control in CAGD and geometric computation is explained, the history and the state-of-the-art of these problems are reviewed, and then some examples are given to illustrate the significance of interval operation.
First, we study the interval implicitization of rational B-spline surfaces. This problem is the generation of the case of curves which is useful to surface operations, such as seeking the intersection of two tangent surfaces. Instead of the method used in the case of curves in which searching the centric curve is followed by searching the boundary curves, we directly seek the boundary surfaces of the interval implicit surface. By introducing the distance, energy and normal direction of the interval surface that determine the geometric shape, we establish an optimization model and give the algorithm of this problem. We give some examples illustrating the algorithm and discuss the application of this method.
Secondly, we study degree reduction of interval spline surfaces. Degree reduction overcomes the contradiction between reducing the complexity of geometric process and avoiding the geometric information loss. Degree reduction of tensor product interval spline surfaces, triangular partition interval spline surfaces over polygonal domain and interval PS surfaces are respectively discussed.
Thirdly, we study the number of the "zero" s of a univariate interval polynomial. Seeking the roots of polynomials is a very important job, but computer float error restricts its applications. In this thesis, we introduce interval polynomials which avoid the information loss. The definition of "zero" and its multiplicity are presented. Then we generalize Descartes rule, Budan-Fourier theorem and Sturm theorem for polynomials to interval polynomials.
Finally, we study the number of "intersection" s of two multivariate interval polynomials and generalize Bezout theorem which determine the number of the intersections of two algebraic curves.
引文
[1] A. Eiger, K. Sikorski and F. Stenger, A bisection method for systems of nonlinear equations, ACM Transactions on Mathematical Software (TOMS), 10(4), 367-377, 1984.
[2] A. Neumaier, Interval iteration for zeros of systems of equations, BIT 25(1), 256-273, 1985.
[3] A.P. Morgan, A method for computing all solutions to systems of polynomial equations, ACM Transactions on Mathematical Software 9, 1-17, 1983.
[4] B. Buchberger, Grobner bases: An algorithmic method in polynomial ideal theory, Multidimensional Systems Theory (N.K. Bose, ed.), 184-232, 1985.
[5] B.R. Piper, Visually smooth interpolation with triangular Bezier patches, Geometric Modeling:Algorithms and new trends, SIAM, 221-234,1987.
[6] C.Y. Hu, Towards robust interval solid modeling for curved objects, PhD Thesis Massachusetts Institute of Technology, Cambridge, 1995.
[7] C.Y. Hu, T. Maekawa, E.C. sherbrooke and N. M. Patrikalakis, Robust interval algorithm for curve intersections, CAD, (28), 495-506, 1996.
[8] C.Y. Hu, N.M. Patrikalakis and X.Z. Ye, Robust interval solid modelling:Part I, representations, Computer Aided Design, 28(10), 807-818, 1996.
[9] C.Y. Hu, N.M. Patrikalakis and X.Z. Ye, Robust interval solid modelling:Part II, boundary evaluation, Computer Aided Design, 28(10), 818-830, 1996.
[10] C.Y. Hu, N.M. Patrikalakis and X.Z. Ye, Robust interval algorithm for surface intersections, Computer Aided Design, 29(9), 617-627, 1996.
[11] C. K. Yap, Exact geometric computation, In Proc 5th Canad. Conf. Comput. Geom., 405-419, 1993.
[12] D. Cox, J. Little and D. O'Shea, Ideas, Varieties and Algorithms: An Introduction to Computational Algebraic Geometry, Springer, New York, 1992.
[13] D. Hertz, C.S. Adjiman and C.A. Floudas, Two results on bounding the roots of interval polynomials, Computers and Chemical Engineering, (23), 1333-1339, 1999.
[14] D. Toth, On ray tracing parametric surfaces, ACM Computer Graphics, 19(3), 171- 179, 1985.
[15] D.M. Wang, A simple method for implicitizing rational curves and surfaces, J. Symbolic Comput., 38(1), 899-914, 2004.
[16] D.Y. Liu, J. Hoschek, GC~1 continuity conditions between adjacent rectangular and triangular Bezier surface patches, Computer Aided Design, 21(4), 194-200, 1989.
[17] E.R. Hansen, A globally convergent interval method for computing and bounding real roots, BIT 18, (4), 415-424, 1978.
[18] E.R. Hansen and S. Sengupta, Bounding solutions of systems of equations using interval arithmetic, BIT 21, 203-211, 1981.
[19] E.R. Hansen and G. William Walster, Sharp Bounds on Interval Polynomial Roots, Reliable Computing,(8), 115-122, 2002.
[20] E. Wurm and B. Juttler, Approximate implicitization via curve fitting, Eurographics Symposium on Geometry Processing, 240-248, 2003.
[21] F.L. Chen and W. Yang, Degree reduction of disk Bezier curves. Computer Aided Geometric Design, 21, 263-280, 2004.
[22] F.L. Chen and W.P. Lou, Degree reduction of interval Bezier Curves, Computer Aided Design, (32), 571-582, 2000.
[23] F.L. Chen, X.F. Yang and W. Yang, Degree reduction of interval B-Spline curves, Journal of Chinese Software, (13), 490-500, 2002.
[24] F.L. Chen and L. Deng, Interval implicitization of rational curves. Computer Aided Geometric Design, 21(4), 401-415, 2004.
[25] F.L. Chen and W. Wang, The μ-basis of a planar rational curve-properties and computation, Graphical Models 64, 368-381, 2003.
[26] G. Farin, A construction for the visual C~1 continuity of polynomical surface patches, Computer graphics and image processing, 20, 272-282, 1982.
[27] G. Farin, Piecewise triangular C~1 surface strips, Computer Aided Design, 18(1), 45-47, 1986.
[28] G. Farin, Curves and Surfaces for CAGD—A Practical Guide, 5th ed. Morgan Kauf- mann Publishers, San Francisco. 2002.
[29] H. Li and S.Q. Liu, Local interpolation of curvature-continuous surfaces, Computer Aided Design, 24(9), 491-503, 1992.
[30] H.W. Lin, L. Lin and G.J. Wang, Boundary evaluation for interval Bezier curve, Computer Aided Design, (34), 637-646, 2002.
[31] I.J. Schoenberg, Contributions to the Problem of Application of Equidistant Data by Analytic Functions,Quart,Appl.Math.,Vol.4,45-99,112-141,1946.
[32] J.A. Ferreira, F. Patncio and F. Oliveira, A priori estimates for the zeros of interval polynomials, Journal of Computational and Applied Mathematics, (136), 271-281, 2001.
[33] J.A. Ferreira, F. Patncio and F. Oliveira, On the computation of solutions of systems of interval polynomial equations, Journal of Computational and Applied Mathemat- ics,(173),295-302,2005.
[34]J.E.Cope and B.W.Rust,Bounds on solutions of linear systems with inaccurate data,SIAM J.Numer.Anal.(16),950-963,1979.
[35]J,Rohn,Systems of linear interval equations,Linear Algebra and Its Appl.,(126),39-78,1989.
[36]J.Rohn,Overestimations in bounding solutions of perturbed linear equations,Linear Algebra and Its Appl.,(262),55-65,1997.
[37]J.M.Snyder,Interval analysis for computer graphics,ACM Computer Graphics,26(2),121-130,1992.
[38]L.Velho and J.Gomes,Approximate conversion from parametric to implicit surfaces,Computer Graphics Forum,15(5),327-337,1996.
[39]M.Karasick,D.Lieber and L.R.Nackman,Efficient Delaunay triangulations using rational arithmetic,ACM Trans.Graph.,10(1):71-91,1991.
[40]Li,M.,Gao,X.S.and Chou,S.C..Quadratic approximation to plane parametric curves and its application in approximate implicitization.Visual Computer,22(9),906-917,2006.
[41]M.Powell and M.Sabin,Piecewise quadratic approximations on triangles,ACM Transactions on Mathematical Software,3,316-325,1977.
[42]M.Segal and C.Seguin,Consistent calculations for solid modeling,Proc.1st ACM Symp.on Computational Geometry Baltimore.MD,5-7,ACM,New York,29-38,1985.
[43]M.Segal,Using tolerances to guarantee valid polyhedral modeling results,In Proceedings of ACM Siggraph,105-114,1990.
[44]M.A.Sabin,The use of piecewise forms for the numerical representation of shape,Ph.D thesis,Hungarian Academy of Sciences,Budapest,Hungary,1976.
[45]M.A.Watkins and A.J.Worsey,Degree reduction of Bézier curves.Computer-Aided Design,20(7),398-405,1988.
[46]P.Dierckx,Curves and Surfaces Fitting with Splines,Oxford University Press,Oxford.1993.
[47]P.Dierckx,On calculating normalized Powell-Sabin B-splines,Computer Aided Geometric Design,15(1),61-78,1997.
[48]Q.Lin and J.G.Rokne,Disk Bézier curves,Computer Aided Geometric Design,(15),721-737,1998.
[49]R.Baker Kearfott,Some tests of generalized bisection,ACM Transactions on Mathematical Software(TOMS),13(3),197-220,1987.
[50] R.E. Barnhill, Smooth interpolation over triangles, Computer Aided Geometric Design, academic press, 1974.
[51] R.E. Barnhill, W. Beohm, Surfaces in Computer Aided Geometric Design, 1983.
[52] R.E. Moore, Interval Analysis, Prentice Hall, Englewood Cliffs, NJ, 1966.
[53] S. Fang, B. Bruderlin and X. Zhu, Robustness in solid modeling: a tolerance-based intuitionistic approach, Computer Aided Design, 25(9), 567-576, 1993.
[54] S.M. Hu, Z. Zuo and J.G. Sun, Approximate degree reduction of triangular Bezier surfaces. Tsinghua Science and Technology, 3(2), 1001-1004, 1998.
[55] S.P. Mudur and P.A. Koparkar, Interval methods for processing geometric objects, IEEE Computer Graph Appl., 4(2), 7-17, 1984.
[56] S.P. Shary, Outer estimation of generalized solution sets to interval linear systems, SIAM J. Numer. Anal, (32), 610-630, 1995.
[57] S.T. Tuohy, T. Maekawa, G. Shen and N.M. Patrikalakis, Approximation of measured data with interval B-Splines, Computer Aided Design, 29(11), 791-799, 1997.
[58] T. Dokken, Approximate implicitization, in Mathematical Methods in CAGD, T. Lyche, L.L. Schumaker(eds), Vanderbilt University Press, Nashville & London, 2001.
[59] T. Duff, Interval arithmetic and recursive subdivision for implicit functions and constructive solid geometry, Computer Graphics, 26(2), 131-138, 1992.
[60] T.W. Sederberg, J.M. Zheng, K. Klimaszewski and T. Dokken, Approximate Implicitization Using Monoid Curves and Surfaces, Graphical Models and Image Processing, (61), 177-198, 1999.
[61] T.W. Sederberg and F.L. Chen , Implicitization using moving curves and surfaces, Proc. SIGGRAPH '95, ACM Press, New York, 301-308, 1995.
[62] V. Kreinovich, A.V. Lakeev and S.I. Noskov, Optimal solution of interval linear systems is intractable (NP-hard), Interval Comput., 6-14, 1993.
[63] W. Boehm, G. Farin and J. Kahmaan, A survey of curve and surface methods in CAGD, Computer Aided Geometric Design, 1, 1-60, 1984.
[64] W. Oettli and W. Prager, Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides, Numer. Math., (6), 405-409, 1964.
[65] W. Oettli, On the solution set of a linear system with inaccurate coefficients, SIAM J. Numer. Anal., (2), 115-118, 1965.
[66] W.J. Gordon and R.F Riesenfeld, B-spline curves and surfaces. In Computer Aided Geometric Design, Academic press, 95-126, 1974.
[67] W.J. Gordon and R.F. Riesenfeld, Bernstein-Bezier Mehtods for the Computer- Aided Design of Free-Form Curves and surfaces.JACM,21(2),293-310,1974.
[68]X.C.Fan,J.S.Deng and F.L.Chen,Zeros of univariate interval polynomials,JCAM,Available online 12 June 2007.
[69]X.S.Gao and M.Li,Approximate Implicitization of Planar Parametric Curves using Quadratic Splines,Mathematics Mechanization Research,21,52-63,2002.
[70]陈发来,有理曲线的近似隐式化表示,计算机学报,21(9),855-859,1998.
[71]陈效群,娄文平,有理曲线的区间Bézier曲线的逼近,中国科学技术大学学报,31(4),379-385,2001.
[72]陈越强,吴卉,邓建松,三角域上球形控制点的Bézier曲面的降阶逼近,中国科学技术大学学报,37(7),777-784,2007.
[73]樊旭川,陈发来,有理B样条曲线的区间隐式化,软件学报,15(6),960-967,2004.
[74]樊旭川,区间多项式与区间隐式化方法,博士学位论文,中国科技大学数学系,2005.
[75]康宝生,石茂,张景峤,有理Bézier曲线的降阶,软件学报,15(10),1522-1527,2004.
[76]刘利刚,王国瑾,寿华好,区间Bézier曲面逼近,计算机辅助设计与图形学学报,12(9),645-650,2000.
[77]李亚娟,陈文喻,汪国昭,有理曲面的区间隐式化,计算机辅助设计与图形学学报,18(7),936-941,2006.
[78]孙红兵,陈效群,李怀远,区间有理曲线的降阶,中国科学技术大学学报,36(9),968-973,2006.
[79]吴卉,邓建松,球形控制点的Bézier曲面的降阶逼近,中国科学技术大学学报,36(6),582-589,2006.
[80]吴文俊,几何定理机器证明的基本原理(初等几何部分),科学出版社,北京,1984。英译本(1994):Mechanical Theorem Proving in Geometries:Base Principles Springer,Wien New York.
[81]王东明,夏壁灿,计算机代数,清华大学出版社,2004.
[82]杨勤民,杨勋年,汪国昭,区间三角Bézier曲面的降阶逼近,软件学报,13(11),2176-2182,2002.
[83]杨周旺,邓建松,陈发来,基于近似几何误差的动态隐式曲线重构,软件学报,15(6),960-969,2004.
[2] A. Neumaier, Interval iteration for zeros of systems of equations, BIT 25(1), 256-273, 1985.
[3] A.P. Morgan, A method for computing all solutions to systems of polynomial equations, ACM Transactions on Mathematical Software 9, 1-17, 1983.
[4] B. Buchberger, Grobner bases: An algorithmic method in polynomial ideal theory, Multidimensional Systems Theory (N.K. Bose, ed.), 184-232, 1985.
[5] B.R. Piper, Visually smooth interpolation with triangular Bezier patches, Geometric Modeling:Algorithms and new trends, SIAM, 221-234,1987.
[6] C.Y. Hu, Towards robust interval solid modeling for curved objects, PhD Thesis Massachusetts Institute of Technology, Cambridge, 1995.
[7] C.Y. Hu, T. Maekawa, E.C. sherbrooke and N. M. Patrikalakis, Robust interval algorithm for curve intersections, CAD, (28), 495-506, 1996.
[8] C.Y. Hu, N.M. Patrikalakis and X.Z. Ye, Robust interval solid modelling:Part I, representations, Computer Aided Design, 28(10), 807-818, 1996.
[9] C.Y. Hu, N.M. Patrikalakis and X.Z. Ye, Robust interval solid modelling:Part II, boundary evaluation, Computer Aided Design, 28(10), 818-830, 1996.
[10] C.Y. Hu, N.M. Patrikalakis and X.Z. Ye, Robust interval algorithm for surface intersections, Computer Aided Design, 29(9), 617-627, 1996.
[11] C. K. Yap, Exact geometric computation, In Proc 5th Canad. Conf. Comput. Geom., 405-419, 1993.
[12] D. Cox, J. Little and D. O'Shea, Ideas, Varieties and Algorithms: An Introduction to Computational Algebraic Geometry, Springer, New York, 1992.
[13] D. Hertz, C.S. Adjiman and C.A. Floudas, Two results on bounding the roots of interval polynomials, Computers and Chemical Engineering, (23), 1333-1339, 1999.
[14] D. Toth, On ray tracing parametric surfaces, ACM Computer Graphics, 19(3), 171- 179, 1985.
[15] D.M. Wang, A simple method for implicitizing rational curves and surfaces, J. Symbolic Comput., 38(1), 899-914, 2004.
[16] D.Y. Liu, J. Hoschek, GC~1 continuity conditions between adjacent rectangular and triangular Bezier surface patches, Computer Aided Design, 21(4), 194-200, 1989.
[17] E.R. Hansen, A globally convergent interval method for computing and bounding real roots, BIT 18, (4), 415-424, 1978.
[18] E.R. Hansen and S. Sengupta, Bounding solutions of systems of equations using interval arithmetic, BIT 21, 203-211, 1981.
[19] E.R. Hansen and G. William Walster, Sharp Bounds on Interval Polynomial Roots, Reliable Computing,(8), 115-122, 2002.
[20] E. Wurm and B. Juttler, Approximate implicitization via curve fitting, Eurographics Symposium on Geometry Processing, 240-248, 2003.
[21] F.L. Chen and W. Yang, Degree reduction of disk Bezier curves. Computer Aided Geometric Design, 21, 263-280, 2004.
[22] F.L. Chen and W.P. Lou, Degree reduction of interval Bezier Curves, Computer Aided Design, (32), 571-582, 2000.
[23] F.L. Chen, X.F. Yang and W. Yang, Degree reduction of interval B-Spline curves, Journal of Chinese Software, (13), 490-500, 2002.
[24] F.L. Chen and L. Deng, Interval implicitization of rational curves. Computer Aided Geometric Design, 21(4), 401-415, 2004.
[25] F.L. Chen and W. Wang, The μ-basis of a planar rational curve-properties and computation, Graphical Models 64, 368-381, 2003.
[26] G. Farin, A construction for the visual C~1 continuity of polynomical surface patches, Computer graphics and image processing, 20, 272-282, 1982.
[27] G. Farin, Piecewise triangular C~1 surface strips, Computer Aided Design, 18(1), 45-47, 1986.
[28] G. Farin, Curves and Surfaces for CAGD—A Practical Guide, 5th ed. Morgan Kauf- mann Publishers, San Francisco. 2002.
[29] H. Li and S.Q. Liu, Local interpolation of curvature-continuous surfaces, Computer Aided Design, 24(9), 491-503, 1992.
[30] H.W. Lin, L. Lin and G.J. Wang, Boundary evaluation for interval Bezier curve, Computer Aided Design, (34), 637-646, 2002.
[31] I.J. Schoenberg, Contributions to the Problem of Application of Equidistant Data by Analytic Functions,Quart,Appl.Math.,Vol.4,45-99,112-141,1946.
[32] J.A. Ferreira, F. Patncio and F. Oliveira, A priori estimates for the zeros of interval polynomials, Journal of Computational and Applied Mathematics, (136), 271-281, 2001.
[33] J.A. Ferreira, F. Patncio and F. Oliveira, On the computation of solutions of systems of interval polynomial equations, Journal of Computational and Applied Mathemat- ics,(173),295-302,2005.
[34]J.E.Cope and B.W.Rust,Bounds on solutions of linear systems with inaccurate data,SIAM J.Numer.Anal.(16),950-963,1979.
[35]J,Rohn,Systems of linear interval equations,Linear Algebra and Its Appl.,(126),39-78,1989.
[36]J.Rohn,Overestimations in bounding solutions of perturbed linear equations,Linear Algebra and Its Appl.,(262),55-65,1997.
[37]J.M.Snyder,Interval analysis for computer graphics,ACM Computer Graphics,26(2),121-130,1992.
[38]L.Velho and J.Gomes,Approximate conversion from parametric to implicit surfaces,Computer Graphics Forum,15(5),327-337,1996.
[39]M.Karasick,D.Lieber and L.R.Nackman,Efficient Delaunay triangulations using rational arithmetic,ACM Trans.Graph.,10(1):71-91,1991.
[40]Li,M.,Gao,X.S.and Chou,S.C..Quadratic approximation to plane parametric curves and its application in approximate implicitization.Visual Computer,22(9),906-917,2006.
[41]M.Powell and M.Sabin,Piecewise quadratic approximations on triangles,ACM Transactions on Mathematical Software,3,316-325,1977.
[42]M.Segal and C.Seguin,Consistent calculations for solid modeling,Proc.1st ACM Symp.on Computational Geometry Baltimore.MD,5-7,ACM,New York,29-38,1985.
[43]M.Segal,Using tolerances to guarantee valid polyhedral modeling results,In Proceedings of ACM Siggraph,105-114,1990.
[44]M.A.Sabin,The use of piecewise forms for the numerical representation of shape,Ph.D thesis,Hungarian Academy of Sciences,Budapest,Hungary,1976.
[45]M.A.Watkins and A.J.Worsey,Degree reduction of Bézier curves.Computer-Aided Design,20(7),398-405,1988.
[46]P.Dierckx,Curves and Surfaces Fitting with Splines,Oxford University Press,Oxford.1993.
[47]P.Dierckx,On calculating normalized Powell-Sabin B-splines,Computer Aided Geometric Design,15(1),61-78,1997.
[48]Q.Lin and J.G.Rokne,Disk Bézier curves,Computer Aided Geometric Design,(15),721-737,1998.
[49]R.Baker Kearfott,Some tests of generalized bisection,ACM Transactions on Mathematical Software(TOMS),13(3),197-220,1987.
[50] R.E. Barnhill, Smooth interpolation over triangles, Computer Aided Geometric Design, academic press, 1974.
[51] R.E. Barnhill, W. Beohm, Surfaces in Computer Aided Geometric Design, 1983.
[52] R.E. Moore, Interval Analysis, Prentice Hall, Englewood Cliffs, NJ, 1966.
[53] S. Fang, B. Bruderlin and X. Zhu, Robustness in solid modeling: a tolerance-based intuitionistic approach, Computer Aided Design, 25(9), 567-576, 1993.
[54] S.M. Hu, Z. Zuo and J.G. Sun, Approximate degree reduction of triangular Bezier surfaces. Tsinghua Science and Technology, 3(2), 1001-1004, 1998.
[55] S.P. Mudur and P.A. Koparkar, Interval methods for processing geometric objects, IEEE Computer Graph Appl., 4(2), 7-17, 1984.
[56] S.P. Shary, Outer estimation of generalized solution sets to interval linear systems, SIAM J. Numer. Anal, (32), 610-630, 1995.
[57] S.T. Tuohy, T. Maekawa, G. Shen and N.M. Patrikalakis, Approximation of measured data with interval B-Splines, Computer Aided Design, 29(11), 791-799, 1997.
[58] T. Dokken, Approximate implicitization, in Mathematical Methods in CAGD, T. Lyche, L.L. Schumaker(eds), Vanderbilt University Press, Nashville & London, 2001.
[59] T. Duff, Interval arithmetic and recursive subdivision for implicit functions and constructive solid geometry, Computer Graphics, 26(2), 131-138, 1992.
[60] T.W. Sederberg, J.M. Zheng, K. Klimaszewski and T. Dokken, Approximate Implicitization Using Monoid Curves and Surfaces, Graphical Models and Image Processing, (61), 177-198, 1999.
[61] T.W. Sederberg and F.L. Chen , Implicitization using moving curves and surfaces, Proc. SIGGRAPH '95, ACM Press, New York, 301-308, 1995.
[62] V. Kreinovich, A.V. Lakeev and S.I. Noskov, Optimal solution of interval linear systems is intractable (NP-hard), Interval Comput., 6-14, 1993.
[63] W. Boehm, G. Farin and J. Kahmaan, A survey of curve and surface methods in CAGD, Computer Aided Geometric Design, 1, 1-60, 1984.
[64] W. Oettli and W. Prager, Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides, Numer. Math., (6), 405-409, 1964.
[65] W. Oettli, On the solution set of a linear system with inaccurate coefficients, SIAM J. Numer. Anal., (2), 115-118, 1965.
[66] W.J. Gordon and R.F Riesenfeld, B-spline curves and surfaces. In Computer Aided Geometric Design, Academic press, 95-126, 1974.
[67] W.J. Gordon and R.F. Riesenfeld, Bernstein-Bezier Mehtods for the Computer- Aided Design of Free-Form Curves and surfaces.JACM,21(2),293-310,1974.
[68]X.C.Fan,J.S.Deng and F.L.Chen,Zeros of univariate interval polynomials,JCAM,Available online 12 June 2007.
[69]X.S.Gao and M.Li,Approximate Implicitization of Planar Parametric Curves using Quadratic Splines,Mathematics Mechanization Research,21,52-63,2002.
[70]陈发来,有理曲线的近似隐式化表示,计算机学报,21(9),855-859,1998.
[71]陈效群,娄文平,有理曲线的区间Bézier曲线的逼近,中国科学技术大学学报,31(4),379-385,2001.
[72]陈越强,吴卉,邓建松,三角域上球形控制点的Bézier曲面的降阶逼近,中国科学技术大学学报,37(7),777-784,2007.
[73]樊旭川,陈发来,有理B样条曲线的区间隐式化,软件学报,15(6),960-967,2004.
[74]樊旭川,区间多项式与区间隐式化方法,博士学位论文,中国科技大学数学系,2005.
[75]康宝生,石茂,张景峤,有理Bézier曲线的降阶,软件学报,15(10),1522-1527,2004.
[76]刘利刚,王国瑾,寿华好,区间Bézier曲面逼近,计算机辅助设计与图形学学报,12(9),645-650,2000.
[77]李亚娟,陈文喻,汪国昭,有理曲面的区间隐式化,计算机辅助设计与图形学学报,18(7),936-941,2006.
[78]孙红兵,陈效群,李怀远,区间有理曲线的降阶,中国科学技术大学学报,36(9),968-973,2006.
[79]吴卉,邓建松,球形控制点的Bézier曲面的降阶逼近,中国科学技术大学学报,36(6),582-589,2006.
[80]吴文俊,几何定理机器证明的基本原理(初等几何部分),科学出版社,北京,1984。英译本(1994):Mechanical Theorem Proving in Geometries:Base Principles Springer,Wien New York.
[81]王东明,夏壁灿,计算机代数,清华大学出版社,2004.
[82]杨勤民,杨勋年,汪国昭,区间三角Bézier曲面的降阶逼近,软件学报,13(11),2176-2182,2002.
[83]杨周旺,邓建松,陈发来,基于近似几何误差的动态隐式曲线重构,软件学报,15(6),960-969,2004.