A fast algorithm for parametric curve plotting

In parametric curve plotting by means of line segments, a curve r = r(t), t[t₀, t_u] is given, and a set of ordered points r(t_i, iN, t_ie[t₀, t_u] is specified as the vertices of an inscribed polygon of the curve. There are several, analytical, numerical or intuitive ways to derive these vertices obtaining a smooth polygonal approximation. The methods, which can be found in the literature, either belong to some special curves or involve a considerable waste of computing time.

In this paper, we consider an algorithm that appears as a subroutine in the whole program. The subroutine allows the main program to space points as a function of a distance interval for any parametric curve. The design of the routine for performing this spacing is outlined and two examples are shown.     

Analytic-numerical solutions with a priori error bounds for time-dependent mixed partial differential problems

The aim of this paper is double. First, we point out that the hypothesis D(t₁)D(t₂) = D(t₂)D(t₁) imposed in [1] can be removed. Second, a constructive method for obtaining analytic-numerical solutions with a prefixed accuracy in a bounded domain Ω(t₀,t₁) = [0,p] × [t₀,t₁], for mixed problems of the type u_t(x,t) − D(t)u_xx(x,t) = 0, 0 < x < p, t> 0, subject to u(0,t) = u(p,t) = 0 and u(x,0) = F(x) is proposed. Here, u(x,t) and F(x) are r-component vectors, D(t) is a C^{r × r} valued analytic function and there exists a positive number δ such that every eigenvalue z of (1/2) (D(t) + D(t)^H) is bigger than δ. An illustrative example is included.     

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.     

Analytic numerical solution of coupled semi-infinite diffusion problems

In this paper, we consider coupled semi-infinite diffusion problems of the form u_t(x, t)− A² u_xx(x,t) = 0, x> 0, t> 0, subject to u(0,t)=B and u(x,0)=0, where A is a matrix in , and u(x,t), and B are vectors in . Using the Fourier sine transform, an explicit exact solution of the problem is proposed. Given an admissible error and a domain D(x₀,t₀)={(x,t);0≤x≤x₀, t≥t₀ > 0, an analytic approximate solution is constructed so that the error with respect to the exact solution is uniformly upper bounded by in D(x₀, t₀).     

Nonlinear robust stabilization of multi-parameter families of systems

We show that given any family of asymptotically stabilizable LTI systems depending continuously on a parameter that lies in some subset [a₁,b₁]××[a_p,b_p] of , there exists a C⁰ time-varying state feedback law v(t,x) (resp. a C⁰ time-invariant feedback law v(x)) which robustly globally exponentially stabilizes (resp. which robustly stabilizes, not asymptotically) the family. Further, if these systems are obtained by linearizing some nonlinear systems, then v(t,x) locally exponentially stabilizes these nonlinear systems. Finally, v(t,x) globally exponentially stabilizes any time-varying system which switches “slowly enough” between the given LTI systems.     

Constructible functions in cellular automata and their applications to hierarchy results

We investigate time-constructible functions in one-dimensional cellular automata (CA). It is shown that (i) if a function t(n) is computable by an O(t(n)−n)-time Turing machine, then t(n) is time constructible by CA and (ii) if two functions are time constructible by CA, then the sum, product, and exponential functions of them are time constructible by CA. As an application, it is shown that if t₁(n) and t₂(n) are time constructible functions such that lim_n→∞ t₁(n)/t₂(n) = 0 and t₁(n)n, then there is a language which can be recognized by a CA in t₂(n) time but not by any CA in t₁(n) time.     

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.     

Integral averages and oscillation of second-order nonlinear differential equations

We present some criteria for the oscillation of the second-order nonlinear differential equation

Full-size image

where a ε C¹([t₀, ∞)) is a nonnegative function, q ε C ([t₀, ∞)) are allowed to change sign on [t₀, ∞), ψ, f ε C¹ , ψ(x) > 0, xf(x) > 0, f′(x) ≥ 0 for x ≠ 0. These criteria are obtained by using a general class of the parameter functions H(t,s) in the averaging techniques and represent extension, as well as improvement of known oscillation criteria of Philos and Purnaras for the generalized Emden-Fowler equation.     

Computation of optimal composite re-parameterizations

Rational re-parameterizations of a polynomial curve that preserve the curve degree and [0,1] parameter domain are characterized by a single degree of freedom. The “optimal” re-parameterization in this family (that comes closest under the L₂ norm to arc-length parameterization) can be identified by solving a quadratic equation, but may exhibit too much residual parametric speed variation for motion control and other applications. Closer approximations to arc-length parameterizations require more flexible re-parameterization functions, such as piecewise-polynomial/rational forms. We show that, for fixed nodes, the optimal piecewise-rational parameterization of the same degree is defined by a simple recursion relation, and we analyze its convergence to the arc-length parameterization. With respect to the new curve parameter, this representation is only of C⁰ continuity, although the smoothness and geometry of the curve are unchanged. A C¹ parameterization can be obtained by using continuity conditions, rather than optimization, to fix certain free parameters, but the objective function is then highly non-linear and does not admit a closed-form optimization. Empirical results from implementations of these methods are presented.     

Biinfinite words with maximal recurrent unbordered factors

A finite non-empty word z is said to be a border of a finite non-empty word w if w=uz=zv for some non-empty words u and v. A finite non-empty word is said to be bordered if it admits a border, and it is said to be unbordered otherwise. In this paper, we give two characterizations of the biinfinite words of the form ^ωuvu^ω, where u and v are finite words, in terms of its unbordered factors.

The main result of the paper states that the words of the form ^ωuvu^ω are precisely the biinfinite words w=a₋₂a₋₁a₀a₁a₂ for which there exists a pair (l₀,r₀) of integers with l₀<r₀ such that, for every integers ll₀ and rr₀, the factor a_la_l0a_r0a_r is a bordered word.

The words of the form ^ωuvu^ω are also characterized as being those biinfinite words w that admit a left recurrent unbordered factor (i.e., an unbordered factor of w that has an infinite number of occurrences “to the left” in w) of maximal length that is also a right recurrent unbordered factor of maximal length. This last result is a biinfinite analogue of a result known for infinite words.     

Constructing space-filling curves of compact connected manifolds

Let M be a compact connected (topological) manifold of finite- or infinite-dimension n. Let 0 r 1 be arbitrary but fixed. We construct in this paper a space-filling curve f from [0,1] onto M, under which M is the image of a compact set A of Hausdorff dimension r. Moreover, the restriction of f to A is one-to-one over the image of a dense subset provided that 0 r log|2ⁿ/log(2ⁿ + 2). The proof is based on the special case where M is the Hilbert cube [0,1]^ω.     

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.     

Lyapunov exponents of the logistic map with periodic forcing

The iterative map x_n+1 = r_nx_n (1 - x_n) is investigated with r_n changing periodically between two values A and B. Different periodicities are assumed, e.g., {r_n} = {BABA …} or {r_n} = {BBABA BBABA …}. The Lyapunov exponent (a measure of average stability) is displayed with high resolution on the A-B-plane. The resulting images have aesthetically appealing self-similar structures. Furthermore, these images allow with one glimpse the identification of a number of system properties: coexistence of attractors, superstable curves, order by alternation of chaotic processes, and chaos by periodic resetting from a stable into an unstable fixed point.     

Generalization of rectangular element stiffness matrix and thermal load vector associated with a0 + a1x + a2y + a3xy type interpolation rule

Explicit expressions for the element stiffness matrix K and element load vector p for the rectangular plane-stress and plane-strain finite elements associated with Ψ(x, y) = a₀ + a₁x + a₂y + a₃xy type interpolation rule are given for the general anisotropic material in xy-planc subjected to non-uniform temperature increases. The expressions are optimized with respect to the numerical operations required for the computation of K and p, and they are valid for special cases of material properties and thermal loading.     

Undecidable properties of monoids with word problem solvable in linear time

Let C₁ be the class of finitely presented monoids with word problem solvable in linear time. Let P be a Markov property of monoids related to class C₁ in some sense. It is undecidable given a monoid in C₁ whether it satisfies P. Let C and C′ be classes of finitely presented monoids with word problem solvable in some time-bounds. If C contains C₁ and C′ properly contains C, then it is undecidable given a monoid in C′ whether it belongs to C.     

The method of resolvents: A technique for the implicitization, inversion, and intersection of non-planar, parametric, rational cubic curves

Let P(t) be a non-planar, parametric, rational cubic curve. The method of resolvents is applied to: (1) construct three quadric surfaces whose intersection is equal to P(t) (implicitization); (2) solve for the parameter t as the ratio of two linear expressions in the coordinates x, y, z (inversion). The results of these two operations are then applied to construct an optimal, robust, intersection algorithm for any two non-planar rational cubic curves, and it is shown that two such curves can intersect in at most five points. Specializations of these results for non-planar, integral, cubic curves are derived, and extensions of these techniques to non-planar, rational cubic, Bézier curves are also discussed.     

Finding the minimum vertex distance between two disjoint convex polygons in linear time

Let V = v₁, v₂, …, v_m and W = w₁, w₂, …, w_n be two linearly separable convex polygons whose vertices are specified by their cartesian coordinates in order. An algorithm with O(m + n) worst-case time complexity is described for finding the minimum euclidean distance between a vertex v₁ in V and a vertex w_j in W. It is also shown that the algorithm is optimal.     

Finite element estimates of singularity powers for cracks terminating at finite width interfaces

Finite elements are used to estimate singularity powers for a crack tip perpendicularly terminating at a material interface. The influence of material stacking sequence upon singularity power estimates is considered as function of bond line width. The ratio of bond line elastic modulus (E₂) to that of the crack containing material (E₁) is used to define the various cases considered (m = E₂/E₁) The width of the bond line is found to have some influence upon singularity powers. It is found that for m < 1.0 the material stacking sequence has little effect upon singularity powers. Conversely, for m > 1.0 the material stacking sequence is found to have the most significant influence upon singularity powers as a function of bond line width. The variation of crack tip stresses for various material combinations and bond line widths is also considered.     

Initial-interval driven biasing of nodal concentration along a fixed curve

Element size transitioning in the construction of spatial meshes for finite element models is often controlled by biasing the concentration of nodes, towards one end or the other, along each of a set of curves in the model. A simple, common and efficient scheme to implement such nodal concentration biasing along a given curve is to require that the nodal spacings δ_i be (sequence) terms bⁱδ₀ of a geometric series. Current practice takes the parameter value b, or its equivalent, as an independent input, so that the initial nodal spacing δ₀ must be a computed output. This is the most straightforward approach, but the lack of direct control over the value δ₀ is a significant shortcoming. In an element size transitioning scenario, δ₀ is often a parameter for which the model builder/analyst has independent quantitative information. It may represent the a priori known thickness of a thin bond or weld, for example. A more rational choice for these cases, proposed by this paper, is a scheme for which δ₀ is an independent input parameter instead of b. The parameter b is computed by a convergence-guaranteed algorithm for which the existence of b as a single-valued function of its input is proven.     

A new way of counting n

In this paper, we shall give a combinatorial proof of the following equation:

,

where m and n are positive integers, m ≤ n, and k₁, k₂, …, k_n-1 are nonnegative integers.