Least-Squares B-Spline Curve Approximation with Arbitary End Derivatives

An algorithm for least-squares approximation of data with end derivative constraints is presented. The approximating curve minimises the error in the least-squares sense, while at the same time assumes the derivatives specified. For degree p approximation, up to p 2 1 derivatives may be specified, resulting in C p−1 continuous curve approximants. The method is useful to piece individual curve segments together, or to create closed curves with various degrees of smoothness.     

Curve interpolation with directional constraints for engineering design

An algorithm to interpolate data points with directional constraints is given in this paper. The interpolating B-spline curve passes through the data points and assumes tangent directions at arbitrarily selected points. The advantages of the method is that the user is free to select any number of directional constraints and the method produces full parametric continuity up to C ^{p − 1} for any degree p interpolation. The method is a generalization of Piegl and Tiller (The NURBS book, 2nd edn. Springer, New York, 1997] in two directions: (1) there is no restriction on the degree, and (2) no need to specify derivatives at all data points.     

参数曲面上的插值与混合

如何表示曲面上的曲线,在处理诸如数控加工中的路径设计以及CAD/CAM等领域频繁出现的曲面裁剪问题时显得日益重要.给出了数据点的切方向(切方向及曲率向量或测地曲率值)指定而G¹连续(G²连续)插值曲面上任意点列的方法.作为曲面上曲线插值问题的特例,还讨论了曲面上曲线的混合问题.基本思想是借助于微分几何的有关结论,曲面上曲线的插值问题被转化为其参数平面上类似的曲线插值问题.该方法能够用二维隐式方程来表示曲面上的插值曲线,从而把在显示该曲线时所面对的曲面求交的几何问题转化为计算隐式曲线的代数问题.实验证明该方法是可行的,而且适用于CAD/CAM及计算机图形学等领域.     

A Multi‐sided Bézier Patch with a Simple Control Structure

A new n‐sided surface scheme is presented, that generalizes tensor product Bézier patches. Boundaries and corresponding cross‐derivatives are specified as conventional Bézier surfaces of arbitrary degrees. The surface is defined over a convex polygonal domain; local coordinates are computed from generalized barycentric coordinates; control points are multiplied by weighted, biparametric Bernstein functions. A method for interpolating a middle point is also presented. This Generalized Bézier (GB) patch is based on a new displacement scheme that builds up multi‐sided patches as a combination of a base patch, n displacement patches and an interior patch; this is considered to be an alternative to the Boolean sum concept. The input ribbons may have different degrees, but the final patch representation has a uniform degree. Interior control points—other than those specified by the user—are placed automatically by a special degree elevation algorithm. GB patches connect to adjacent Bézier surfaces with G¹continuity. The control structure is simple and intuitive; the number of control points is proportional to those of quadrilateral control grids. The scheme is introduced through simple examples; suggestions for future work are also discussed.     

Matrix-valued 4-point spline and 3-point non-spline interpolatory curve subdivision schemes

The objective of this paper is to study and construct matrix-valued templates for interpolatory curve subdivision. Since our investigation of this problem was motivated by the need of such subdivision stencils as boundary templates for interpolatory surface subdivision, we provide both spline and non-spline templates that are necessarily symmetric, due to the lack of direction-orientation in carrying out surface subdivision in general. For example, the minimum-supported Hermite interpolatory C¹ cubic spline curve subdivision scheme, with the skew-symmetric basis function for interpolating first derivatives, does not meet the symmetry specification. Non-spline C² interpolatory templates constructed in this paper are particularly important, due to their smaller support needed to minimize undesirable surface oscillations, when adopted as boundary templates for interpolatory C² surface subdivision. The curve subdivision templates introduced in this paper are adopted as boundary stencils for interpolatory surface subdivision with matrix-valued templates.     

Uniform trigonometric polynomial B-spline curves

This paper presents a new kind of uniform spline curve, named trigonometric polynomial B-splines, over space Ω = span{sini,cost, tk-3,tk-4, …,t, 1} of which k is an arbitrary integer larger than or equal to 3. We show that trigonometric polynomial B-spline curves have many similar properties to traditional B-splines. Based on the explicit representation of the curve we have also presented the subdivision formulae for this new kind of curve. Since the new spline can include both polynomial curves and trigonometric curves as special cases without rational form, it can be used as an efficient new model for geometric design in the fields of CAD/CAM.     

Error analysis of the derivative of rational interpolation with a linear denominator

This paper deals with the approximation properties of the derivatives of rational cubic interpolation with a linear denominator. Error expressions of the derivatives of interpolating functions are derived, convergence is established and the optimal error coefficient c _i is proved to be symmetric about the parameters of the rational interpolation. The unified integral form of the error of the second derivative in all subintervals is obtained. A simple expression of the jump of the second derivative at the knots and the conditions for the interpolating function to be C ² in the interpolating interval are given.     

Blaschke products and optimal recovery inH ∞

We examine the error in the optimal estimation of∫ ₋₁ ¹ f(t)w(t)dt by a quadrature formula using values off at equally spaced points of (−1, 1) or at the zeros of ultraspherical polynomials. Heref is known to be an analytic function in the unit disc which is bounded by l andw is a given weight function with prescribed behavior near ±1. A major role in our investigations is played by bounds on (−1, 1) from above and below for the finite Blaschke product which is based in the nodes of the quadrature formula. Optimal estimation of the functionf, rather than its integral, is also studied.     

Curve fitting and fairing using conic splines

We present an efficient geometric algorithm for conic spline curve fitting and fairing through conic arc scaling. Given a set of planar points, we first construct a tangent continuous conic spline by interpolating the points with a quadratic Bézier spline curve or fitting the data with a smooth arc spline. The arc spline can be represented as a piecewise quadratic rational Bézier spline curve. For parts of the G¹ conic spline without an inflection, we can obtain a curvature continuous conic spline by adjusting the tangent direction at the joint point and scaling the weights for every two adjacent rational Bézier curves. The unwanted curvature extrema within conic segments or at some joint points can be removed efficiently by scaling the weights of the conic segments or moving the joint points along the normal direction of the curve at the point. In the end, a fair conic spline curve is obtained that is G² continuous at convex or concave parts and G¹ continuous at inflection points. The main advantages of the method lies in two aspects, one advantage is that we can construct a curvature continuous conic spline by a local algorithm, the other one is that the curvature plot of the conic spline can be controlled efficiently. The method can be used in the field where fair shape is desired by interpolating or approximating a given point set. Numerical examples from simulated and real data are presented to show the efficiency of the new method.     

利用距离与内能极小平滑链接Bézier曲线

目的 对于满足低阶连续的链接Bézier曲线,提高曲线之间的连续性以达到平滑的目的,需要对曲线的控制顶点进行相应调整。因此,可根据具体的目标对需要调整的控制顶点进行优化选取,使得平滑后的链接曲线满足相应的要求。针对这一问题,给出了3种目标下优化调整控制顶点的方法。方法 首先对讨论的问题进行描述,分别指出链接Bézier曲线从C⁰连续平滑为C¹连续和从C¹连续平滑为C²连续两种情形需调整的控制顶点;然后分别给出两种情形下,以新旧控制顶点距离极小为目标、曲线内能极小为目标、新旧控制顶点距离与曲线内能同时极小为目标,对链接Bézier曲线进行平滑的方法,最后对3种极小化方法进行对比,并指出了不同方法的适用场合。结果 数值算例表明,距离极小化方法调整后的控制顶点偏离原控制顶点的距离相对较小,适合于控制顶点取自于实物时的应用场合;内能极小化方法获得的链接曲线内能相对较小,适合于要求曲线能量尽可能小的应用场合;距离与内能同时极小化方法兼顾了新旧控制顶点的距离和链接曲线的内能,适合于对两个目标都有要求的应用场合。结论 提出的方法为链接Bézier曲线的平滑提供了3种有效手段,且易于实现,对其他类型链接曲线的平滑具有参考价值。     

单变量均匀静态细分格式的连续性分析和构造

利用单变量均匀稳定细分格式C^k连续的充要条件,分析了已有的插值曲线格式各阶连续时参数的取值范围.首次指出了六点二重插值格式可以达到C³连续,并构造了一种新的C³连续的六点三重插值细分格式.     

Wavelength Assignment for Realizing Parallel FFT on Regular Optical Networks

Routing and wavelength assignment (RWA) is a central issue to increase efficiency and reduce cost in Wavelength Division Multiplexing (WDM) optical networks. In this paper, we address the problem of wavelength assignment for realizing parallel FFT on a class of regular optical WDM networks. We propose two methods for sequential mapping and shift-reversal mapping of FFT communication pattern to the optical WDM networks concerned. By sequential mapping, the numbers of wavelengths required to realize parallel FFT with 2ⁿ nodes on WDM linear arrays, rings, 2-D meshes and 2-D tori are 2^{n − 1}, 2^{n − 1}, 2^{max (k,n − k) − 1} and 2^{max (k,n − k) − 1} respectively. By shift-reversal mapping, the numbers of wavelengths required are max (3× 2^{n − 3},2), 2^{n − 2}, max (3× 2^{max (k,n − k) − 3},2) and 2^{max (k,n − k) − 2}. These results show that shift-reversal mapping outperforms sequential mapping. Our results have a clear significance for applications because FFT represents a common computation pattern shared by a large class of scientific and engineering problems and WDM optical networks as a promising technology in networking has an increasing popularity.     

Ternary butterfly subdivision

This paper presents an interpolating ternary butterfly subdivision scheme for triangular meshes based on a 1–9 splitting operator. The regular rules are derived from a C² interpolating subdivision curve, and the irregular rules are established through the Fourier analysis of the regular case. By analyzing the eigenstructures and characteristic maps, we show that the subdivision surfaces generated by this scheme is C¹ continuous up to valence 100. In addition, the curvature of regular region is bounded. Finally we demonstrate the visual quality of our subdivision scheme with several examples.     

Filling n-sided regions with NURBS patches

n -sided region with G ^ɛ continuous NURBS patches that interpolate boundary curves and approximate given cross-boundary derivatives. The NURBS surfaces joining along inner or boundary curves have normal vectors that do not deviate more than the user-specified angular tolerance ɛ. The method is general in that there are no restrictions on the number of boundary curves, and the cross-boundary derivatives can be specified independently. To satisfy all conditions, only one degree elevation is needed.     

Parallel algorithms for finding polynomial Roots on OTIS-torus

We present two parallel algorithms for finding all the roots of an N-degree polynomial equation on an efficient model of Optoelectronic Transpose Interconnection System (OTIS), called OTIS-2D torus. The parallel algorithms are based on the iterative schemes of Durand–Kerner and Ehrlich methods. We show that the algorithm for the Durand–Kerner method requires (N ^0.75+0.5N ^0.25−1) electronic moves + 2(N ^0.5−1) OTIS moves using N processors. The parallel algorithm for Ehrlich method is shown to run in (N ^0.75+0.5N ^0.25−1) electronic moves + 2(N ^0.5−1) OTIS moves with the same number of processors. The algorithms have lower AT cost than the algorithms presented in Jana (Parallel Comput 32:301–312, 2006). The scalability of the algorithms is also discussed.     

C3连续的单位四元数插值样条曲线

目的 构造一类C³连续的单位四元数插值样条曲线,证明它的插值性和连续性,并把它应用于刚体关键帧动画设计中。方法 利用R³空间中插值样条曲线的5次多项式调配函数的累和形式构造了S³空间中单位四元数插值样条曲线,它不仅能精确通过一系列给定的方向,而且能生成C³连续的朝向曲线。结果 与Nielson的单位四元数均匀B样条插值曲线的迭代构造方法相比,所提方法避免了为获取四元数B样条曲线控制顶点对非线性方程组迭代求解的过程,提高了运算效率;与单位四元数代数三角混合插值样条曲线的构造方法（Su方法）相比,所提方法只用到多项式基,运算速度更快。本例中创建关键帧动画所需的时间与Nielson方法和Su方法相比平均下降了73%和33%。而且,相比前两种方法,所提方法产生的四元数曲线连续性更高,由C²连续提高到C³连续,这意味着动画中刚体的朝向变化更加自然。结论 仿真结果表明,本文方法对刚体关键帧动画设计是有效的,对实时性和流畅性要求高的动画设计场合尤为适用。     

Data Mining with Sparse Grids

O (h _n ⁻¹ n ^{d −1}) instead of O(h _n ^−d ) grid points and unknowns are involved. Here d denotes the dimension of the feature space and h _n = 2 ⁻ⁿ gives the mesh size. To be precise, we suggest to use the sparse grid combination technique [42] where the classification problem is discretized and solved on a certain sequence of conventional grids with uniform mesh sizes in each coordinate direction. The sparse grid solution is then obtained from the solutions on these different grids by linear combination. In contrast to other sparse grid techniques, the combination method is simpler to use and can be parallelized in a natural and straightforward way. We describe the sparse grid combination technique for the classification problem in terms of the regularization network approach. We then give implementational details and discuss the complexity of the algorithm. It turns out that the method scales only linearly with the number of instances, i.e. the amount of data to be classified. Finally we report on the quality of the classifier built by our new method. Here we consider standard test problems from the UCI repository and problems with huge synthetical data sets in up to 9 dimensions. It turns out that our new method achieves correctness rates which are competitive to that of the best existing methods. Received April 25, 2001     

Disuguaglianze relative all'approssimazione polinomiale in norma uniforme

Let Π _n denote the space of algebraic polynomials of degreen or less. In this paper we establish the inequality for everyf _∈ C ⁽ⁿ⁻¹⁾ ([−1, 1]) andf ⁽ⁿ⁻¹⁾ absolutely continuous. A way for obtaining similar inequalities forf _∈ C ^(t−1) ([−1, 1]) andf ^(l−1) absolutely continuous is given.

---

---

Ricerca effettuata mentre l'autore fruiva di una Borsa di Studio del C.N.R.     

Approximate Range Searching in External Memory

In this paper, we present two linear-size external memory data structures for approximate range searching. Our first structure, the BAR-B-tree, stores a set of N points in ℝ ^d and can report all points inside a query range Q by accessing O(log  _B N+ε ^γ +k _ε /B) disk blocks, where B is the disk block size, γ=1−d for convex queries and γ=−d otherwise, and k _ε is the number of points lying within a distance of ε⋅diam (Q) to the query range Q. Our second structure, the object-BAR-B-tree, is able to store objects of arbitrary shapes of constant complexity and provides similar query guarantees. In addition, both structures can support other types of range searching queries such as range aggregation and nearest-neighbor. Finally, we present I/O-efficient algorithms to build these structures.     

Il metodo di Treffiz-Fichera per i semigruppi. potenziale di tipo potenza

A variation of the Trefftz-Fichera method is presented to compute lower bounds for the eigenvalues of a positive self-adjoint operator with discrete spectrum with grow at least in a logarithmic way as the index diverges. As suggested by Barnes et al. [2] to compute ground state, the semigroupe ^−βH, β>0, is used rather than the iterated resolvent(H+β) ⁻ⁿ,n=1,2,... As an example, the method is applied to the operatorH=−Δ+|x|^γ. inL ²(R), 1≤γ≤4.