Shape preserving interpolation by curvature continuous parametric curves

An interpolation scheme for planar curves is described, obtained by patching together parametric cubic segments and straight lines. The scheme has, in general, geometric continuity of order 2 (G² continuity) and is similar in approach to that of [Goodman & Unsworth ′86], but whereas this earlier scheme, when applied to cubics, produces curves with zero curvature at the interpolation points, the corresponding curvature values in this scheme are in general non-zero. The choice of a tangent vector at each interpolation point guarantees that the interpolating curve is local convexity preserving, and in the case of functional data it is single-valued and local monotonicity preserving. The algorithm for generating the cubic curve segments usually requires the solution of two non-linear equations in two unknowns, and lower bounds are obtained on the magnitude of the curvature at the relevant interpolation points in order that this system of equations has a unique solution. Particular attention is given to cubic segments which are adjacent to straight line segments. Two methods for calculating these segments are described, one which preserves G² continuity, and one which only gives G¹ continuity. A number of examples of the application of the scheme are presented.     

Efficient enumeration of all minimal separators in a graph

This paper presents an efficient algorithm for enumerating all minimal a-b separators separating given non-adjacent vertices a and b in an undirected connected simple graph G = (V, E), Our algorithm requires O(n³R_ab) time, which improves the known result of O(n⁴R_ab) time for solving this problem, where ¦V¦= n and R_ab is the number of minimal a-b separators. The algorithm can be generalized for enumerating all minimal A-B separators that separate non-adjacent vertex sets A, B < V, and it requires O(n²(n − n_A − n_b)R_AB) time in this case, where n_a = ¦A¦, n_B = ¦B¦ and r_AB is the number of all minimal A−B separators. Using the algorithm above as a routine, an efficient algorithm for enumerating all minimal separators of G separating G into at least two connected components is constructed. The algorithm runs in time O(n³R⁺_Σ + n⁴R_Σ), which improves the known result of O(n⁶R_Σ) time, where R_σ is the number of all minimal separators of G and R_ΣR⁺_Σ = ∑_1i, v_j) ER_vivj n − 1)/2 − m)R_Σ. Efficient parallelization of these algorithms is also discussed. It is shown that the first algorithm requires at most O((n/log n)R_ab) time and the second one runs in time O((n/log n)R⁺_Σ+n log nR_Σ) on a CREW PRAM with O(n³) processors.     

G interpolation of free form curve networks by biquintic Gregory patches

The problem of interpolating a free form curve network with irregular topology is investigated in order to create a curvature continuous surface. The spanning curve segments are parametric quintic polynomials, the interpolating surface elements are biquintic Gregory patches. A necessary compatibility condition is formulated and proved which need to be satisfied at each node of the curve network. Constraints are derived for assuring G² continuity between biquintic Gregory patches, which share a common side or a common corner point. The above conditions still leave certain geometric freedom for defining the entire G² surface, so following some analysis a particular construction is presented, by which after computing the principle curvatures at each node the free parameters are locally set for each interpolating Gregory patch.     

On the global linearization of bilinear systems

The problem of finding a global state space transformation to transform a given single-input homogeneous bilinear system to a controllable linear system on Rⁿ is considered here. We show that the existence of a solution of the above problem is equivalent to the existence of a local state space transformation that carries the corresponding bilinear system locally to a controllable linear one. The complete analysis of the globally state linearizable bilinear systems in R² and R³ is also included.     

Gregory-type patches bounded by low degree intergral curves for G continuity

G² continuity of free-form surfaces is sometimes very important in engineering applications. The conditions for G² continuity to connect two Bézier patches were studied and methods have been developed to ensure it. However, they have some restrictions on the shapes of patches of the Bézierpatch formulation. Gregory patch is a kind of free-form surface patch which is extended from Bézier patch so that four first derivatives on its boundary curves can be specified without restrictions of the compatibility condition. Several types of Gregory patches have been developed for intergral, rational, and NURBS boundary curves. In this paper, we propose some intergral boundary Gregorytype patches bounded by cubic and quartic curves for G² continuity.     

On Stieltjes functions and Hankel operators

Let G be a Stieltjes function which is analytic in the open right half plane. It is shown that G is in H^∞(RHP) if and only if the Hankel operator H_G on H²(RHP) with symbol G is nuclear. If G is in H^∞(RHP) it is shown that the non-tangential limit of G at s = 0 equals twice the nuclear norm of H_G.     

Algorithms of discretization of algebraic spatial curves on homogeneous cubical grids

In this paper new methods of discretization (integer approximation) of algebraic spatial curves in the form of intersecting surfaces P(x, y, z) = 0 and Q(x, y, z) = 0 are analyzed.

The use of homogeneous cubical grids G(h³) to discretize a curve is the essence of the method. Two new algorithms of discretization (on 6-connected grid G_6c(h³) and 26-connected grid G₂₆(h³)) are presented based on the method above. Implementation of the algorithms for algebraic spatial curves is suggested. The elaborated algorithms are adjusted for application in computer graphics and numerical control of machine tools.     

Extended Games–Chan algorithm for the 2-adic complexity of FCSR-sequences

Binary sequences generated by feedback shift registers with carry operation (FCSR) share many of the important properties enjoyed by sequences generated by linear feedback shift registers. We present an FCSR analog of the (extended) Games–Chan algorithm, which efficiently determines the linear complexity of a periodic binary sequence with period length T = 2ⁿ or pⁿ, where p is an odd prime and 2 is a primitive element modulo p². The algorithm to be presented yields an upper bound for the 2-adic complexity, an FCSR analog of the linear complexity, of a pⁿ-periodic binary sequence.     

Ensuring compatibility of G-continuous surface patches around a nodepoint

The problem of ensuring compatibility of mixed partial derivative vectors of surface patches joining G²-continuously around a common nodepoint is essential in modelling G²-continuous n-sided surfaces. Although the compatibility constraints can be removed by using C² Gregory patches, these patches have singularities at their corner points. This paper presents conditions for ensuring the compatibility of the mixed partial derivative vectors of surface patches joining G²-continuously around a common nodepoint. After investigating the solvability of these compatibility conditions, a new solution method exploiting G³-continuity of surface patches at a common nodepoint is given. Example surfaces based on this solution method are also provided.     

Decidability results for primitive recursive algorithms

In this paper I use the notion of trace defined in (Theoret. Comput. Sci. 266 (2001) 159) to extend Coquand's constructive proof (C. R. Acad. Sci. Ser. I 314 (1992)) of the ultimate obstination theorem of Colson to the case when mutual recursion is allowed. As a by-product I get an algorithm that computes the value of a primitive recursive combinator applied to lazy integers (infinite or partially undefined arguments may appear). I also get, as Coquand got from his proof, that, even when mutual recursion is allowed, there is no primitive recursive definition f such that f(Sⁿ())=Sⁿ²().     

Integration of beam functions

The beam functions satisfying d⁴φ/dξ⁴ = β⁴φ with the associated boundary conditions are convenient admissible comparison functions for the approximated solutions of complex structural problems by the well known Rayleigh-Ritz method. Reliable integration formulae for products of various beam functions φ and ψ with an arbitrary function θ are essential. Felgar's recurrence formula for ∫ θφψ dξ is found to be in error and is corrected here. The condition when the characteristic values of θ and ψ are identical is also considered. A simple subroutine is given to evaluate ∫ θ(ξ)(dⁿφ/dξⁿ)(d^mψ/dξ^mdξ for all possible sets of boundary conditions. Applications to the free vibration of nonuniform beams and plate systems are demonstrated.     

Experimental numerical studies on a supercomputer of natural convection in an enclosure with localized heating

We present particle simulations of natural convection of a symmetrical, nonlinear, three-dimensional cavity flow problem. Qualitative studies are made in an enclosure with localized heating. The assumption is that particles interact locally by means of a compensating Lennard-Jones type force F, whose magnitude is given by −G/r^p + H/r^q.

In this formula, the parameters G, H, p, q depend upon the nature of the interacting particles and r is the distance between two particles. We also consider the system to be under the influence of gravity. Assuming that there are n particles, the equations relating position, velocity and acceleration at time t_k = kΔt, K = 0, 1, 2, …, are solved simultaneously using the “leap-frog” formulas. The basic formulas relating force and acceleration are Newton's dynamical equations F_i,k = m_ia_i,k, I = 1, 2, 3, …, n, where m_i is the mass of the ith particle.

Extensive and varied computations on a CRAY X - MP/24 are described and discussed, and comparisons are made with the results of others.     

Steering high order moment calculations from lower dimensional spaces

In this study we consider some well established algorithms used to determine separating hyperplanes for sets in Rⁿ. We implement these algorithms in a high dimensional tensor space that is affiliated with representing the higher order moment information for the sets in question. We identify an inner product preserving morphism from tensor space to Rⁿ. Using the morphism, the calculations of the algorithm are brought down to a space of much lower dimension. Our results make it clear that higher order moment computations can often avoid the burden of computation in a high dimensional vector space.     

Resolvability and the upper dimension of graphs

For an ordered set W = {w₁, w₂,…, w_k} of vertices and a vertex v in a connected graph G, the (metric) representation of v with respect to W is the k-vector r(v | W) = (d(v, w₁), d(v, w₂),…, d(v, w_k)), where d(x, y) represents the distance between the vertices x and y. The set W is a resolving set for G if distinct vertices of G have distinct representations. A new sharp lower bound for the dimension of a graph G in terms of its maximum degree is presented.

A resolving set of minimum cardinality is a basis for G and the number of vertices in a basis is its (metric) dimension dim(G). A resolving set S of G is a minimal resolving set if no proper subset of S is a resolving set. The maximum cardinality of a minimal resolving set is the upper dimension dim⁺(G). The resolving number res(G) of a connected graph G is the minimum k such that every k-set W of vertices of G is also a resolving set of G. Then 1 ≤ dim(G) ≤ dim⁺(G) ≤ res(G) ≤ n − 1 for every nontrivial connected graph G of order n. It is shown that dim⁺(G) = res(G) = n − 1 if and only if G = K_n, while dim⁺(G) = res(G) = 2 if and only if G is a path of order at least 4 or an odd cycle.

The resolving numbers and upper dimensions of some well-known graphs are determined. It is shown that for every pair a, b of integers with 2 ≤ a ≤ b, there exists a connected graph G with dim(G) = dim⁺(G) = a and res(G) = b. Also, for every positive integer N, there exists a connected graph G with res(G) − dim⁺(G) ≥ N and dim⁺(G) − dim(G) ≥ N.     

Blossoms are polar forms

Consider the functions H(t):=t² and h(u,v):=uv. The identity H(t)=h(t,t) shows that h is the restriction of h to the diagonal u=v in the uv-plane. Yet, in many ways, a bilinear function like h is simpler than a homogeneous quadratic function like H. More generally, if F(t) is some n-ic polynomial function, it is often helpful to study the polar form of F, which is the unique symmetric, multiaffine function ƒ(u_1,…u_n) satisfying the identity F(t)=f(t,…,t). The mathematical theory underlying splines is one area where polar forms can be particularly helpful, because two pieces F and G of an n-ic spline meet at a point r with C^k parametric continuity if and only if their polar forms ƒ and g agree on all sequences of n arguments that contain at least n-k copies of r.

The polar approach to the theory of splines emerged in rather different guises in three independent research efforts: Paul de Faget Casteljau called it ‘shapes through poles’; Carl de Boor called it ‘B-splines without divided differences’; and Lyle Ramshaw called it ‘blossoming’. This paper reviews the work of de Casteljau, de Boor, and Ramshaw in an attempt to clarify the basic principles that underly the polar approach. It also proposes a consistent system of nomenclature as a possible standard.     

Computation of eigenpairs of Ax = γBx for vibrations of spinning deformable bodies

It is shown that, when linear theory is used, the general eigenvalue problem related with the free vibrations of spinning deformable bodies is of the type Ax = γBx, where A is Hermitian, and B is real positive definite. Since the order n of the matrices may be large, and A and B are banded or block banded, due to the economics of the numerical solution, one is interested in obtaining only those eigenvalues which fall within the frequency band of interest of the problem. The paper extends the well known method of bisections and iteration of Rⁿ to n dimensional complex spaces, i.e. to Cⁿ, so that it can be applied to the present problem.     

Bivariate hermite subdivision

A subdivision scheme for constructing smooth surfaces interpolating scattered data in R³ is proposed. It is also possible to impose derivative constraints in these points. In the case of functional data, i.e., data are given in a properly triangulated set of points {(x_i, y_i)}_i=1^N from which none of the pairs (x_i,y_i) and (x_j,y_j) with i≠j coincide, it is proved that the resulting surface (function) is C¹. The method is based on the construction of a sequence of continuous splines of degree 3. Another subdivision method, based on constructing a sequence of splines of degree 5 which are once differentiable, yields a function which is C² if the data are not ‘too irregular’. Finally the approximation properties of the methods are investigated.     

On some dynamical subsets of the rauzy fractal

Let ( ,(+1)_n) be the adic system associated to the substitution: 1 → 12,…,(n − 1) → 1n, n → 1. In Sirvent (1996) it was shown that there exist a subset Cⁿ of and a map h_n: C → Cⁿ such that the dynamical system (C, h_n) is semiconjugate to ( ). In this paper we compute the Hausdorff and Billingsley dimensions of the geometrical realizations of the set Cⁿ on the (n− l)-dimensional torus. We also show that the dynamical system (Cⁿ,h_n) cannot be realized on the (n − 1)-torus.     

A modification to the rational boundary Gregory patch

This paper presents a method for modifying the boundary derivatives of rational Bézier patches, preserving their directions at any parameter so as not to affect the G¹ continuity with adjacent patches. This method is applicable to reduce the complexity of rational boundary Gregory patches.     

Convexity-preserving fairing

This paper develops a two-stage automatic algorithm for fairing C²-continuous cubic parametric B-splines under convexity, tolerance and end constraints. The first stage is a global procedure, yielding a C² cubic B-spline which satisfies the local-convexity, local-tolerance and end constraints imposed by the designer. The second stage is a local finefairing procedure employing an iterative knot-removal knotreinsertion technique, which adopts the curvature-slope discontinuity as the fairness measure of a C² spline. This procedure preserves the convexity and end properties of the output of the first stage and, moreover, it embodies a globaltolerance constraint. The performance of the algorithm is discussed for four data sets.