有理曲线的多项式逼近

利用曲线摄动的思想给出了用多项式曲线逼近有理曲线的一种新方法．其基本步骤是对有理曲线的控制顶点进行摄动，使之产生一多项式曲线，并使摄动误差在某种范数意义之下达到最小．同时，通过适当控制摄动曲线的顶点，使逼近多项式曲线与有理曲线在两端点保持一定的连续性．这一结果可以与细分（ｓｕｂｄｉｖｉｓｉｏｎ）技术结合给出有理曲线的整体光滑的分片多项式逼近．实例表明，在某些情况下本文中的方法要优于传统的Ｈｅｒｍｉｔｅ插值方法及Ｔ．Ｗ．Ｓｅｄｅｒｂｅｒｇ和Ｍ．Ｋａｋｉｍｏｔｏ（１９９１）提出的杂交曲线逼近算法．     

有理曲线和曲面的分片多项式逼近

本文利用摄动的思想,以摄动有理曲线（曲面）的系数的无穷模作为优化目标,给出了用多项式曲线（曲面）逼近有理曲线（曲面）的一种新方法．同以前的各种方法相比,该方法不仅收敛而且具有更快的收敛速度,并且可以与细分技术相结合,得到有理曲线与曲面的整体光滑、分片多项式的逼近．     

有理曲线和曲面的分片多项式逼近

本文利用撮动的思想,以摄动有理曲线(曲面)的系数的无穷模怍为优化目标,给出了用多项式曲线(曲面)逼近有理曲线(曲面)的一种新方法．同以前的各种方法相比,该方法不仅收敛而且具有更快的收敛速度,并且可以与细分技术相结合．得到有理曲线与曲面的整体光滑,分片多项式的逼近。     

三次Bézier曲线的快速生成算法

本文给出了一种三次Ｂéｚｉｅｒ曲线的生成算法，在曲线的逐点生成过程中，只用到加减法，故效率极高．而且，此方法可推广到一般多项式或有理参数曲线     

一类有理Bézier曲线及其求积求导的多项式逼近

用多项式曲线来逼近有理曲线在计算机辅助几何设计(CAGD)系统中可简化求积求导等繁琐的计算.然而,按现有的方法能检验一条已知的有理曲线是否具有收敛的多项式逼近曲线却不易选择适当的权因子来产生能用多项式曲线来加以逼近的有理曲线,即不易做到事先设计;同时,要减少求积、求导的逼近误差只能依靠提高多项式曲线的次数.文中给出一类有理Bézier曲线及其多项式逼近算法较好地克服了这两种缺陷,具有推广应用的价值.     

一类特殊多项式整数规划问题的最优化算法

本文考虑了一类特殊的多项式整数规划问题。此类问题有很广泛的实际应用,并且是NP难问题。对于这类问题,最优性必要条件和最优性充分条件已经给出。我们在本文中将要利用这些最优性条件设计最优化算法。首 先,利用最优性必要条件,我们给出了一种新的局部优化算法。进而我们结合最优性充分条件、新的局部优化算法和辅助函数,设计了新的全局最优化算法。本文给出的算例展示出我们的算法是有效的和可靠的。     

圆锥曲线的三次有理多项式参数化

圆锥曲线重新参数化可以提高曲线参数的均匀性,且增强在拼接点处的光滑性.常用的参数化方法是采用一次有理多项式或二次有理多项式.采用三次有理多项式对圆锥曲线重新参数化,使曲线的次数由二次升到六次.以圆弧为例所得的实验结果袁明,在两段圆弧的公共点处的连续性为C~3,而且三次有理多项式参数化与弧长参数化的弦长偏差相比二次有理多项式参数化减小两个数量级.     

一个整数瓶颈问题的两个多项式算法

讨论下列数学模型Ⅰ:求x=(x_1,x_2,…,x_n)适合条件{■a_(ij)x_j≥b_i (i=1,2,…,m) x_j≥0且整数(j=1,2,…,n)使f(x)■{c_jx_j}达到最小值,其中m＜n,a_(ij),b_i及c_j均为正整数。对该模型,建立了两个多项式算法,其复杂度均为O(n~2),并列举了一个数值例子．     

一类有理Bézier曲线的等距线算法及MATLAB实现

构造一类正则有理Bézier曲线,利用改进的有理de casteljau算法求得这类正则有理n次Bézier曲线各点处的切矢,由此得出各点的单位法矢量,应用于原始曲线等距线的计算.该方法几何意义明显,算法简洁,实践效果比较好.同时给出了用Matlab绘制有理Bézier曲线及其等距线的程序,准确快捷,实践效果较好.     

关于分段有理插值的算法

在本中，我们利用Pldé-type逼近厦正变多项式的知识给出了一种计算分段有理插值的算法，它具有快速、简便及精度高的特点。     

A branch-and-bound algorithm for 0–1 parametric mixed integer programming

A branch-and-bound algorithm to solve 0–1 parametric mixed integer linear programming problems has been developed. The present algorithm is an extension of the branch-and-bound algorithm for parametric analysis on pure integer programming. The characteristic of the present method is that optimal solutions for all values of the parameter can be obtained.     

On the distribution of integer points of rational curves

Let F(X,Y) be an absolutely irreducible polynomial in such that the algebraic curve C: F(X,Y) = 0 has infinitely many integer points. In this paper we obtain an explicit estimate on the distribution of integer points of C.     

Hybrid polynomial approximation to higher derivatives of rational curves

In this paper, we extend the results published in JCAM volume 214 pp. 163-174 in 2008. Based on the bound estimates of higher derivatives of both Bernstein basis functions and rational Bézier curves, we prove that for any given rational Bézier curve, if the convergence condition of the corresponding hybrid polynomial approximation is satisfied, then not only the l-th (l=1,2,3) derivatives of its hybrid polynomial approximation curve uniformly converge to the corresponding derivatives of the rational Bézier curve, but also this conclusion is tenable in the case of any order derivative. This result can expand the area of applications of hybrid polynomial approximation to rational curves in geometric design and geometric computation.     

Parameter spaces for curves on surfaces and enumeration of rational curves

Let S be a smooth, minimal rational surface. The geometry of the Severi variety parametrising irreducible, rational curves in a given linear system on S is studied. The results obtained are applied to enumerative geometry, in combination with ideas from Quantum Cohomology. Formulas enumerating rational curves are found, some of which generalised Kontsevich's formula for plane curves.     

A strongly polynomial algorithm for the transportation problem

For the (linear) transportation problem withm supply nodes,n demand nodes andk feasible arcs we describe an algorithm which runs in time proportional tom logm(k + n logn) (assuming w.l.o.g.mn). The algorithm uses excess scaling. The complexity bound is a slight improvement over the bound achieved by an application of a min-cost-flow algorithm of Orlin to the transportation problem.Corresponding author. Research supported in part by grant no. I-84-095.06/88 of the German—Israeli-Foundation for Scientific Research and Development.     

Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming

This paper presents a “standard form” variant of Karmarkar's algorithm for linear programming. The tecniques of using duality and cutting objective are combined in this variant to maintain polynomial-time complexity and to bypass the difficulties found in Karmarkar's original algorithm. The variant works with problems in standard form and simultaneously generates sequences of primal and dual feasible solutions whose objective function values converge to the unknown optimal value. Some computational results are also reported.     

A strongly polynomial algorithm for solving two-sided linear systems in max-algebra

An algorithm for solving m×n systems of (max,+)-linear equations is presented. The systems have variables on both sides of the equations. After O(m⁴n⁴) iterations the algorithm either finds a solution of the system or finds out that no solution exists. Each iteration needs O(mn) operations so that the complexity of the presented algorithm is O(m⁵n⁵).     

An improvement over the GVW algorithm for inhomogeneous polynomial systems

The GVW algorithm provides a new framework for computing Gröbner bases efficiently. If the input system is not homogeneous, some J-pairs with larger signatures but lower degrees may be rejected by GVW's criteria, and instead, GVW has to compute some J-pairs with smaller signatures but higher degrees. Consequently, degrees of polynomials appearing during the computations may unnecessarily grow up higher, and hence, the total computations become more expensive. This phenomenon happens more frequently when the coefficient field is a finite field and the field polynomials are involved in the computations. In this paper, a variant of the GVW algorithm, called M-GVW, is proposed. The concept of mutant pairs is introduced to overcome the inconveniences brought by inhomogeneous inputs. In aspects of implementations, to obtain efficient implementations of GVW/M-GVW over boolean polynomial rings, we take advantages of the famous library M4RI. We propose a new rotating swap method of adapting efficient routines in M4RI to deal with the one-direction reductions in GVW/M-GVW. Our implementations are tested with many examples from Boolean polynomial rings, and the timings show M-GVW usually performs much better than the original GVW algorithm if mutant pairs are found.