Equivalence of distinct characterizations for rational rotation-minimizing frames on quintic space curves

A rotation-minimizing frame on a space curve r(t) is an orthonormal basis (f₁,f₂,f₃) for R³, where f₁=r^′/|r^′| is the curve tangent, and the normal-plane vectors f₂,f₃ exhibit no instantaneous rotation about f₁. Such frames are useful in spatial path planning, swept surface design, computer animation, robotics, and related applications. The simplest curves that have rational rotation-minimizing frames (RRMF curves) comprise a subset of the quintic Pythagorean-hodograph (PH) curves, and two quite different characterizations of them are currently known: (a) through constraints on the PH curve coefficients; and (b) through a certain polynomial divisibility condition. Although (a) is better suited to the formulation of constructive algorithms, (b) has the advantage of remaining valid for curves of any degree. A proof of the equivalence of these two different criteria is presented for PH quintics, together with comments on the generalization to higher-order curves. Although (a) and (b) are both sufficient and necessary criteria for a PH quintic to be an RRMF curve, the (non-obvious) proof presented here helps to clarify the subtle relationships between them.     

AHT Bézier Curves and NUAHT B-Spline Curves

In this paper, we present two new unified mathematics models of conics and polynomial curves, called algebraic hyperbolic trigonometric （ AHT） Bezier curves and non-uniform algebraic hyperbolic trigonometric （ NUAHT） B-spline curves of order n, which are generated over the space span{sin t, cos t, sinh t, cosh t, 1, t,..., t^n-5}, n 7〉 5. The two kinds of curves share most of the properties as those of the Bezier curves and B-spline curves in polynomial space. In particular, they can represent exactly some remarkable transcendental curves such as the helix, the cycloid and the catenary. The subdivision formulae of these new kinds of curves are also given. The generations of the tensor product surfaces are straightforward. Using the new mathematics models, we present the control mesh representations of two classes of minimal surfaces.     

Optimal time byzantine agreement for t <n/8 with linear-messages

Summary.  This paper presents a Byzantine Agreement protocol with n=8t+1, optimal number of rounds (namely min{ f+2, t+1} where f is number of actual faults), and messages of linear size (namely m≦n+O(log n), where m stands for message size). All previous protocols that stop in optimal time and tolerate t=O(n) faults require messages of size at least O(n ²). The new protocol uses a novel technique called Reconstructed Traversal which is based on the Reconstruction Principle and on the Coordinated Traversal protocol. Received: August 1992/Accepted: January 1995l     

Tool-path generation of planar NURBS curves

It has been widely used in CAD field for many years and gradually applied in CAM area with the prevalence of NURBS interpolator equipped in CNC controllers. But few of them provide the tool radius compensation function. In order to achieve the goal of generating tool-path, an algorithm was presented to offset NURBS curves by an optimum process for CAD/CAM systems in this paper. NURBS format is ideal for HSM applications, but not all NURBS outputs are equal and standard. Basically, there are two different ways to generate NURBS tool-paths; one is to fit a NURBS curve to the conventional tool-path output, the other one is to generate a NURBS tool-path from the start. The main targets for the tool-path of this paper are: (1) To keep a constant distance d between progenitor curve C(t) and offset curve C_d(t) on the normal direction of C(t); (2) to alternate the order k of the basis function in offset curve C_d(t); (3) to oscillate the number of control points of offset curve C_d(t) and compare it with progenitor curve C(t). In order to meet the tolerance requirements as specified by the design, this study offsets the NURBS curves by a pre-described distance d. The principle procedure consists of the following steps: (1) construct an evaluating bound error function; (2) sample offset point-sequenced curves based on first derivatives; (3) give the order of NURBS curve and number of control points to compute all initial conditions and (4) optimize the control points by a path searching algorithm.     

Parallel batch scheduling of equal-length jobs with release and due dates

In this paper we study parallel batch scheduling problems with bounded batch capacity and equal-length jobs in a single and parallel machine environment. It is shown that the feasibility problem 1|p-batch,b<n,r _j ,p _j =p,C _j ≤d _j |− can be solved in O(n ²) time and that the problem of minimizing the maximum lateness can be solved in O(n ²log n) time. For the parallel machine problem P|p-batch,b<n,r _j ,p _j =p,C _j ≤d _j |− an O(n ³log n)-time algorithm is provided, which can also be used to solve the problem of minimizing the maximum lateness in O(n ³log ² n) time.     

Möbius变换下四次有理抛物-PH曲线的C2 Hermite插值

目的 曲线插值问题在机器人设计、机械工业、航天工业等诸多现代工业领域都有广泛的应用，而已知端点数据的Hermite插值是计算机辅助几何设计中一种常用的曲线构造方法，本文讨论了一种偶数次有理等距曲线，即四次抛物-PH曲线的C² Hermite插值问题。方法 基于M bius变换引入参数，利用复分析的方法构造了四次有理抛物-PH曲线的C² Hermite插值，给出了具体插值算法及相应的Bézier曲线表示和控制顶点的表达式。结果 通过给出"合理"的端点插值数据，以数值实例表明了该算法的有效性，所得12条插值曲线中，结合最小绝对旋转数和弹性弯曲能量最小化两种准则给出了判定满足插值条件最优曲线的选择方法，并以具体实例说明了与其他插值方法的对比分析结果。结论 本文构造了M bius变换下的四次有理抛物-PH曲线的C² Hermite插值，在保证曲线次数较低的情况下，达到了连续性更高的插值条件，计算更为简单，插值效果明显，较之传统奇数次PH曲线具有更加自然的几何形状，对偶数次PH曲线的相关研究具有一定意义。     

The μ-basis of a planar rational curve—properties and computation

A moving line L(x,y;t)=0 is a family of lines with one parameter t in a plane. A moving line L(x,y;t)=0 is said to follow a rational curve P(t) if the point P(t₀) is on the line L(x,y;t₀)=0 for any parameter value t₀. A μ-basis of a rational curve P(t) is a pair of lowest degree moving lines that constitute a basis of the module formed by all the moving lines following P(t), which is the syzygy module of P(t). The study of moving lines, especially the μ-basis, has recently led to an efficient method, called the moving line method, for computing the implicit equation of a rational curve [3 and 6]. In this paper, we present properties and equivalent definitions of a μ-basis of a planar rational curve. Several of these properties and definitions are new, and they help to clarify an earlier definition of the μ-basis [3]. Furthermore, based on some of these newly established properties, an efficient algorithm is presented to compute a μ-basis of a planar rational curve. This algorithm applies vector elimination to the moving line module of P(t), and has O(n²) time complexity, where n is the degree of P(t). We show that the new algorithm is more efficient than the fastest previous algorithm [7].     

On the system of word equations x i 1 x i 2…x i m=y i 1 y i 2…y i n (i=1, 2, …) in a free monoid

 It is proved that the system of word equations x ⁱ ₁=y ⁱ ₁ y ⁱ ₂…y ⁱ _n , i=1, 2,…, ⌈n/2⌉ +1, has only cyclic solutions. Some sharpenings concerning the cases n=5, 7 and n≥9 are derived as well as results concerning the general system of equations x ⁱ ₁ x ⁱ ₂…x ⁱ _m =y ⁱ ₁ y ⁱ ₂…y ⁱ _n , i=1, 2,… . Applications to test sets of certain bounded languages are considered. Received: 18 May 1995/2 January 1996     

Exponential Stability of Slowly Time-Varying Nonlinear Systems

Let be a time-varying vector field depending on t containing a regular and a slow time scale (α large). Assume there exist a k (τ)≥1 and a γ(τ) such that ∥x _τ(t, t ₀, x ₀)∥≤k(τ) e ^{−γ(τ)(t−t0)}∥x ₀∥, with x _τ(t, t ₀, x ₀) the solution of the parametrized system with initial state x ₀ at t ₀. We show that for α sufficiently large is exponentially stable when “on average”γ(τ) is positive. The use of this result is illustrated by means of two examples. First, we extend the circle criterion. Second, exponential stability for a pendulum with a nonlinear slowly time-varying friction attaining positive and negative values is discussed. Date received: January 22, 2000. Date revised: April 14, 2001.     

Mapping Between 2-D Meshes of the Same Size

1IntroductionInrece11tyears,n1a11yparallelalgoritlImshavebeendesignedtosolvedifferentproblemso1lvario1ls11etworktopologics.Bi11arytrees,meshesandhypercubesarethethreeimportal1tl1etworktop()logieswllicllhaterpcoivedintensivestlldy.WiththeadvanceofVLSI,manyllewl1etworkssuchasstargrapl1[1]havebeenorwiIlbeintroduced.Inor相似文献   

On the Attainable Order of Collocation Methods for the Neutral Functional-Differential Equations with Proportional Delays

In this paper, we extend the recent results of H. Brunner in BIT (1997) for the DDE y′(t)= by(qt), y(0)=1 and the DVIE y(t)=1+∫₀ ^t by(qs)ds with proportional delay qt, 0<q≤1, to the neutral functional-differential equation (NFDE): and the delay Volterra integro-differential equation (DVIDE) : with proportional delays p _i t and q _i t, 0<p _i ,q _i ≤1 and complex numbers a,b _i and c _i . We analyze the attainable order of m-stage implicit (collocation-based) Runge-Kutta methods at the first mesh point t=h for the collocation solution v(t) of the NFDE and the `iterated collocation solution u _it (t)' of the DVIDE to the solution y(t), and investigate the existence of the collocation polynomials M _m (t) of v(th) or M^ _m (t) of u _it (th), t∈[0,1] such that the rational approximant v(h) or u _it (h) is the (m,m)-Padé approximant to y(h) and satisfies |v(h)−y(h)|=O(h ^{2 m +1}). If they exist, then we actually give the conditions of M _m (t) and M^ _m (t), respectively. Received September 17, 1998; revised September 30, 1999     

A note on the Ate pairing

The Ate pairing has been suggested since it can be computed efficiently on ordinary elliptic curves with small values of the traces of Frobenius t. However, not all pairing-friendly elliptic curves have this property. In this paper, we generalize the Ate pairing and find a series of the variations of the Ate pairing. We show that the shortest Miller loop of the variations of the Ate pairing can possibly be as small as r ^1/φ(k) on some special pairing-friendly curves with large values of Frobenius trace, and hence speed up the pairing computation significantly. This work is supported by the National Natural Science Foundation of China (No. 60773202, 60633030) and 973 Program (No. 2006CB303104).     

Fast Algorithms for the Density Finding Problem

We study the problem of finding a specific density subsequence of a sequence arising from the analysis of biomolecular sequences. Given a sequence A=(a ₁,w ₁),(a ₂,w ₂),…,(a _n ,w _n ) of n ordered pairs (a _i ,w _i ) of numbers a _i and width w _i >0 for each 1≤i≤n, two nonnegative numbers ℓ, u with ℓ≤u and a number δ, the Density Finding Problem is to find the consecutive subsequence A(i ^*,j ^*) over all O(n ²) consecutive subsequences A(i,j) with width constraint satisfying ℓ≤w(i,j)=∑ _r=i ^j w _r ≤u such that its density is closest to δ. The extensively studied Maximum-Density Segment Problem is a special case of the Density Finding Problem with δ=∞. We show that the Density Finding Problem has a lower bound Ω(nlog n) in the algebraic decision tree model of computation. We give an algorithm for the Density Finding Problem that runs in optimal O(nlog n) time and O(nlog n) space for the case when there is no upper bound on the width of the sequence, i.e., u=w(1,n). For the general case, we give an algorithm that runs in O(nlog ² m) time and O(n+mlog m) space, where and w _min=min  _r=1 ⁿ w _r . As a byproduct, we give another O(n) time and space algorithm for the Maximum-Density Segment Problem. Grants NSC95-2221-E-001-016-MY3, NSC-94-2422-H-001-0001, and NSC-95-2752-E-002-005-PAE, and by the Taiwan Information Security Center (TWISC) under the Grants NSC NSC95-2218-E-001-001, NSC95-3114-P-001-002-Y, NSC94-3114-P-001-003-Y and NSC 94-3114-P-011-001.     

Approximating Buy-at-Bulk and Shallow-Light <Emphasis Type="Italic">k</Emphasis>-Steiner Trees

We study two related network design problems with two cost functions. In the buy-at-bulk k-Steiner tree problem we are given a graph G(V,E) with a set of terminals T⊆V including a particular vertex s called the root, and an integer k≤|T|. There are two cost functions on the edges of G, a buy cost b:E→ℝ⁺ and a distance cost r:E→ℝ⁺. The goal is to find a subtree H of G rooted at s with at least k terminals so that the cost ∑ _e∈H b(e)+∑ _t∈T−s dist(t,s) is minimized, where dist(t,s) is the distance from t to s in H with respect to the r cost. We present an O(log ⁴ n)-approximation algorithm for the buy-at-bulk k-Steiner tree problem. The second and closely related one is bicriteria approximation algorithm for Shallow-light k-Steiner trees. In the shallow-light k-Steiner tree problem we are given a graph G with edge costs b(e) and distance costs r(e), and an integer k. Our goal is to find a minimum cost (under b-cost) k-Steiner tree such that the diameter under r-cost is at most some given bound D. We develop an (O(log n),O(log ³ n))-approximation algorithm for a relaxed version of Shallow-light k-Steiner tree where the solution has at least terminals. Using this we obtain an (O(log ² n),O(log ⁴ n))-approximation algorithm for the shallow-light k-Steiner tree and an O(log ⁴ n)-approximation algorithm for the buy-at-bulk k-Steiner tree problem. Our results are recently used to give the first polylogarithmic approximation algorithm for the non-uniform multicommodity buy-at-bulk problem (Chekuri, C., et al. in Proceedings of 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), pp. 677–686, 2006). A preliminary version of this paper appeared in the Proceedings of 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) 2006, LNCS 4110, pp. 153–163, 2006. M.T. Hajiaghayi supported in part by IPM under grant number CS1383-2-02. M.R. Salavatipour supported by NSERC grant No. G121210990, and a faculty start-up grant from University of Alberta.     

Euclidean Signature Curves

It is well known that two planar curves that are related by a Euclidean transformation possess the same signature curve. Recently Musso and Nicolodi (J. Math. Imaging Vis. 35:68–85, 2009) gave examples of non-congruent curves that possess the same Euclidean signature curve. In this paper we show how to construct all planar curves of class C ³ that have a given signature curve.     

Existence of set-interpolating and energy-minimizing curves

We consider existence of curves which minimize an energy of the form ∫c^(k)p (k=1,2,… , 1<p<∞) under side-conditions of the form G_j(c(t_1,j),…,c^(k−1)(t_k,j))M_j, where G_j is a continuous function, t_i,j[0,1], M_j is some closed set, and the indices j range in some index set J. This includes the problem of finding energy minimizing interpolants restricted to surfaces, and also variational near-interpolating problems. The norm used for vectors does not have to be Euclidean.It is shown that such an energy minimizer exists if there exists a curve satisfying the side conditions at all, and if among the interpolation conditions there are at least k points to be interpolated. In the case k=1, some relations to arc length are shown.     

Surface approximation to scanned data

A method to approximate scanned data points with a B-spline surface is presented. The data are assumed to be organized in the form of Q _i,j, i=0,…,n; j=0,…,m _i, i.e., in a row-wise fashion. The method produces a C ^{(p-1, q-1)} continuous surface (p and q are the required degrees) that does not deviate from the data by more than a user-specified tolerance. The parametrization of the surface is not affected negatively by the distribution of the points in each row, and it can be influenced by a user-supplied knot vector.     

Ellipse-based principal component analysis for self-intersecting curve reconstruction from noisy point sets

Surface reconstruction from cross cuts usually requires curve reconstruction from planar noisy point samples. The output curves must form a possibly disconnected 1-manifold for the surface reconstruction to proceed. This article describes an implemented algorithm for the reconstruction of planar curves (1-manifolds) out of noisy point samples of a self-intersecting or nearly self-intersecting planar curve C. C:[a,b]⊂R→R ² is self-intersecting if C(u)=C(v), u≠v, u,v∈(a,b) (C(u) is the self-intersection point). We consider only transversal self-intersections, i.e. those for which the tangents of the intersecting branches at the intersection point do not coincide (C′(u)≠C′(v)). In the presence of noise, curves which self-intersect cannot be distinguished from curves which nearly self-intersect. Existing algorithms for curve reconstruction out of either noisy point samples or pixel data, do not produce a (possibly disconnected) Piecewise Linear 1-manifold approaching the whole point sample. The algorithm implemented in this work uses Principal Component Analysis (PCA) with elliptic support regions near the self-intersections. The algorithm was successful in recovering contours out of noisy slice samples of a surface, for the Hand, Pelvis and Skull data sets. As a test for the correctness of the obtained curves in the slice levels, they were input into an algorithm of surface reconstruction, leading to a reconstructed surface which reproduces the topological and geometrical properties of the original object. The algorithm robustly reacts not only to statistical non-correlation at the self-intersections (non-manifold neighborhoods) but also to occasional high noise at the non-self-intersecting (1-manifold) neighborhoods.     

Semigroup generation and stabilization by A-bounded feedback perturbations

Let A be a generator of a strongly continuous semigroup of operators, and assume that C and H are operators such that A + CH generates a strongly continuous semigroup S_H(t) on X. Let λ₀ be a real number in the resolvent set of A, and let ε [−1, 1]. Then there are some fairly unrestrictive conditions under which A+(λ₀ − A)CH(λ₀ − A)⁻ also generates a strongly continuous semigroup S_K(t) on X which has the same exponential growth rate as S_H(t). Given an input operator B, we can use this to identify a class of feedback perturbations K such that A + BK generates a strongly continuous semigroup. We can also use this result to identify classes of feedbacks which can and cannot uniformly stabilize a system. For example, we show that if the control on a cantilever beam in the state space H₀²[0, 1] × L²[0, 1] is a moment force on the free end, then we cannot stabilize the beam with an A^−1/2-bounded feedback, but we can find an A^−1/4-bounded feedback, for any > 0, which does stabilize the beam.     

On the rate of convergence of 2-term recursions in ℝ d

LetG be a compact set in ℝ ^d d≥1,M=G×G andϕ:M →G a map inC ₃(M). Suppose thatϕ has a fixed pointξ, i.e.ϕ(ξ, ξ)=ξ. We investigate the rate of convergence of the iterationx ⁿ⁺²=φ(x ⁿ⁺¹,x ⁿ) withx ⁰,x ¹∈G andx ⁿ→ξ. Iff _n=Q‖x ⁿ−ξ‖ with a suitable norm and a constantQ depending onξ, an exact representation forf _n is derived. The error terms satisfyf _2m+1≍(ƒ_2m)^γ,f _2m+2≍(ƒ_2m+1)^2γ,m≥0, with 1<gg<2, andγ=γ(x ¹,x ⁰). According to our main result we have lim_n→∞{‖x ⁿ⁺²‖/(‖x ⁿ‖)²}=Q, 0<Q<∞. This paper constitutes an extension of a part of the author’s doctoral thesis realized under the direction of Prof. E. Wirsing and Prof. A. Peyerimhoff, University of Ulm (Germany).