On convolutions of algebraic curves

We focus on the investigation of relations between plane algebraic curves and their convolution. Since the convolution of irreducible algebraic curves is not necessarily irreducible, an upper bound for the number of components is given. Then, a formula expressing the convolution degree using the algebraic degree and the genus of the curve is derived. In addition, a detailed analysis of the so-called special and degenerated components is discussed. We also present some special results for curves with low convolution degree and for rational curves, and use our results to investigate the relation with the theory of the classical offsets and Pythagorean Hodograph (PH) curves presented in Arrondo et al. (1997).     

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.     

Rational Pythagorean-hodograph space curves

A method for constructing rational Pythagorean-hodograph (PH) curves in R³ is proposed, based on prescribing a field of rational unit tangent vectors. This tangent field, together with its first derivative, defines the orientation of the curve osculating planes. Augmenting this orientation information with a rational support function, that specifies the distance of each osculating plane from the origin, then completely defines a one-parameter family of osculating planes, whose envelope is a developable ruled surface. The rational PH space curve is identified as the edge of regression (or cuspidal edge) of this developable surface. Such curves have rational parametric speed, and also rational adapted frames that satisfy the same conditions as polynomial PH curves in order to be rotation-minimizing with respect to the tangent. The key properties of such rational PH space curves are derived and illustrated by examples, and simple algorithms for their practical construction by geometric Hermite interpolation are also proposed.     

Blending two parametric curves

Segments of two given curves can be blended to produce a segment of a new curve. Blending can provide a smooth transition from one curve to another and can give various degrees of smoothness at the endpoints of the blend, where the smoothness is measured analogously to parametric continuity C⁽ⁿ⁾ and geometric continuity G⁽ⁿ⁾. Blending can provide an approximation to a given curve segment. The accuracy of the approximation to short segments obtained by different blending formulas is compared via asymptotic analysis. Finally, it is shown how to find a blend that is a parametric polynomial whose parameter is approximately an arc length parameter.     

Partial degree formulae for plane offset curves

In this paper we present several formulae for computing the partial degrees of the defining polynomial of the offset curve to an irreducible affine plane curve given implicitly, and we see how these formulae particularize to the case of rational curves. In addition, we present a formula for computing the degree w.r.t. the distance variable.     

Self-intersection elimination in metamorphosis of two-dimensional curves

H :[0, 1]× ³→ ³, where H(t, r) for t=0 and t=1 are two given planar curves C ₁(r) and C ₂(r). The first t parameter defines the time of fixing the intermediate metamorphosis curve. The locus of H(t, r) coincides with the ruled surface between C ₁(r) and C ₂(r), but each isoparametric curve of H(t, r) is self-intersection free. The second algorithm suits morphing operations of planar curves. First, it constructs the best correspondence of the relative parameterizations of the initial and final curves. Then it eliminates the remaining self-intersections and flips back the domains that self-intersect.     

Optimal affine reparametrization of rational curves

Let K be a characteristic zero field, let ?(t) be a birational parametrization ?(t) of a K-definable curve C with coefficients in an algebraic extension K(α) over K. We propose an algorithm to solve the optimization problem of computing the affine reparametrization t→at+b such that ?(at+b) has coefficients over an extension of K with algebraic degree as small as possible.     

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.     

Algorithms for Del Pezzo surfaces of degree 5 (construction, parametrization)

It is well known that every Del Pezzo surface of degree 5 defined over a field k is parametrizable over k. In this paper, we give an algorithm for parametrizing, as well as algorithms for constructing examples in every isomorphism class and for deciding equivalence.     

Automatic parameterization of rational curves and surfaces III: Algebraic plane curves

We present algorithms to compute the genus and rational parametric equations, for implicitly defined irreducible plane algebraic curves of arbitrary degree. Rational parameterizations exist for all irreducible algebraic curves of genus 0. The genus is computed by a complete analysis of the singularities of plane algebraic curves, using affine quadratic transformations. The rational parameterization techniques, essentially, reduce to solving symbolically systems of homogeneous linear equations and the computation of polynomial resultants.     

Approximate merging of B-spline curves via knot adjustment and constrained optimization

This paper addresses the problem of approximate merging of two adjacent B-spline curves into one B-spline curve. The basic idea of the approach is to find the conditions for precise merging of two B-spline curves, and perturb the control points of the curves by constrained optimization subject to satisfying these conditions. To obtain a merged curve without superfluous knots, we present a new knot adjustment algorithm for adjusting the end k knots of a kth order B-spline curve without changing its shape. The more general problem of merging curves to pass through some target points is also discussed.     

Stability bounds in networks with dynamic link capacities

We address the problem of stability in networks where the link capacities can change dynamically. We show that every network running a greedy scheduling policy is universally stable at any injection rate r<1/(Cd), where d is the largest number of links crossed by any packet and C is the maximum link capacity. We also show that system-wide time priority scheduling policies are universally stable at any injection rate r<1/(C(d−1)).     

Convex hulls of objects bounded by algebraic curves

We present an0(n ·d ^o(1)) algorithm to compute the convex hull of a curved object bounded by0(n) algebraic curve segments of maximum degreed.     

An extension of Kedlaya’s algorithm for hyperelliptic curves

In this paper we describe a generalisation and adaptation of Kedlaya’s algorithm for computing the zeta-function of a hyperelliptic curve over a finite field of odd characteristic that the author used for the implementation of the algorithm in the Magma library. We generalise the algorithm to the case of an even degree model. We also analyse the adaptation of working with the xⁱdx/y³ rather than the xⁱdx/y differential basis. This basis has the computational advantage of always leading to an integral transformation matrix whereas the latter fails to in small genus cases. There are some theoretical subtleties that arise in the even degree case where the two differential bases actually lead to different redundant eigenvalues that must be discarded.     

Compressed piecewise-circular approximations of 3D curves

We propose a compact approximation scheme for 3D curves. Consider a polygonal curve P, whose n vertices have been generated through adaptive (and nearly minimal) sampling, so that P approximates some original 3D curve, O, within tolerance ε₀. We present a practical and efficient algorithm for computing a continuous 3D curve C that approximates P within tolerance ε₁ and is composed of a chain of m circular arcs, whose end-points coincide with a subset of the vertices of P. We represent C using 5m+3 scalars, which we compress within a carefully selected quantization error ε₂. Empirical results show that our approximation uses a total of less than 7.5n bits, when O is a typical surface/surface intersection and when the error bound ε₁+ε₂ is less than 0.02% of the radius of a minimal sphere around O. For less accurate approximations, the storage size drops further, reaching for instance a total of n bits when ε₁+ε₂ is increased to 3%. The storage cost per vertex is also reduced when ε₀ is decreased to force a tighter fit for smooth curves. As expected, the compression deteriorates for jagged curves with a tight error bound. In any case, our representation of C is always more compact than a polygonal curve that approximate O with the same accuracy. To guarantee a correct fit, we introduce a new error metric for ε₁, which prevents discrepancies between P and C that are not detected by previously proposed Hausdorff or least-square error estimates. We provide the details of the algorithms and of the geometric constructions. We also introduce a conservative speed-up for computing C more efficiently and demonstrate that it is sub-optimal in only 2% of the cases. Finally, we report results on several types of curves and compare them to previously reported polygonal approximations, observing compression ratios that vary between 15:1 and 36:1.     

Solving genus zero Diophantine equations over number fields

Let K be a number field and F(X,Y) an absolutely irreducible polynomial of K[X,Y] such that the algebraic curve defined by the equation F(X,Y)=0 is rational. In this paper we present practical algorithms for the determination of all solutions of the Diophantine equation F(X,Y)=0 in algebraic integers of K.     

A sweep-plane algorithm for computing the Euler-characteristic of polyhedra represented in Boolean form

We present an algorithm EULER for the computation of the Euler-characteristic χ(P) of bounded polyhedraP?? ^d . It is first shown that χ(P) is uniquely determined by the local properties ofP at its vertices. It is therefore possible to compute χ(P) using a plane sweeping through ? ^d , collecting the local information available at every vertex. There is a close relationship with an algorithm for the computation of the volumeV (P) published earlier (cf. [4]). The reason is that both ofV and χ are additive functionals.