Perspective silhouette of a general swept volume

We present an efficient and robust algorithm for computing the perspective silhouette of the boundary of a general swept volume. We also construct the topology of connected components of the silhouette. At each instant t, a three-dimensional object moving along a trajectory touches the envelope surface of its swept volume along a characteristic curve K^t. The same instance of the moving object has a silhouette curve L^t on its own boundary. The intersection K^t∩L^t contributes to the silhouette of the general swept volume. We reformulate this problem as a system of two polynomial equations in three variables. The connected components of the resulting silhouette curves are constructed by detecting the instances where the two curves K^t and L^t intersect each other tangentially on the surface of the moving object. We also consider a general case where the eye position changes while moving along a predefined path. The problem is reformulated as a system of two polynomial equations in four variables, where the zero-set is a two-manifold. By analyzing the topology of the zero-set, we achieve an efficient algorithm for generating a continuous animation of perspective silhouettes of a general swept volume.     

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].     

Minimum distance between a canal surface and a simple surface

The computation of the minimum distance between two objects is an important problem in the applications such as haptic rendering, CAD/CAM, NC verification, robotics and computer graphics. This paper presents a method to compute the minimum distance between a canal surface and a simple surface (i.e. a plane, a natural quadric, or a torus) by finding roots of a function of a single parameter. We utilize the fact that the normals at the closest points between two surfaces are collinear. Given the spine curve C(t), t_min≤t≤t_max, and the radius function r(t) for a canal surface, a point on the spine curve uniquely determines a characteristic circle on the surface. Normals to the canal surface at points on form a cone with a vertex and an axis which is parallel to Then we construct a function of t which expresses the condition that the perpendicular from C(t) to a given simple surface is embedded in the cone of normals to the canal surface at points on K(t). By solving this equation, we find characteristic circles which contain the points of locally minimum distance from the simple surface. Based on these circles, we can compute the minimum distance between given surfaces.     

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.     

A result on robust boundedness

We give conditions under which, if, for any fixed p, all the solutions of (1) enter a compact set K_p (depending on p) after a finite time, then all the solutions of (2) ‘tend to’ the moving compact set K_p(t).The differential equation (2) may be obtained when applying a time-varying control law to a system. Non-linear output tracking is concerned.This may also apply to indirect adaptive control when you design such and adaptation law that you have a priori informations about e(t), the equation error, and p(t), the parameter estimate.     

Stochastic stabilization and destabilization

It is shown in this paper that any nonlinear systems in ^d can be stabilized by Brownian motion provided |ƒ(x,t)| ≤ K|x| for some K > 0. On the other hand, this system can also be destabilized by Brownian motion if the dimension d ≥ 2. Similar results are also obtained for any given stochastic differential equation dx(t) = ƒ(x(t), t) + g(x(t), t) dW(t).     

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.     

Stability radii of linear discrete-time systems and symplectic pencils

In this paper, we introduce and analyse robustness measures for the stability of discrete-time system x(t + 1) = Ax(t) under parameter perturbations of the form A→A + BDC where B,C are given matrices. In particular we characterize the stability radius of the uncertain system x(t + 1) = (A + BDC)x(t), D an unknown complex perturbation matrix, via an associated symplectic pencil and present an algorithm for the computation of that radius.     

Stable polyhedra in parameter space

A typical uncertainty structure of a characteristic polynomial is P(s)=A(s)Q(s)+B(s) with A(s) and B(s) fixed and Q(s) uncertain. In robust controller design Q(s) may be a controller numerator or denominator polynomial; an example is the PID controller with Q(s)=K_I+K_Ps+K_Ds². In robustness analysis Q(s) may describe a plant uncertainty. For fixed imaginary part of Q(jω), it is shown that Hurwitz stability boundaries in the parameter space of the even part of Q(jω) are hyperplanes and the stability regions are convex polyhedra. A dual result holds for fixed real part of Q(jω). Also σ-stability with the real parts of all roots of P(s) smaller than σ is treated.Under the above conditions, the roots of P(s) can cross the imaginary axis only at a finite number of discrete “singular” frequencies. Each singular frequency generates a hyperplane as stability boundary. An application is robust controller design by simultaneous stabilization of several representatives of A(s) and B(s) by a PID controller. Geometrically, the intersection of convex polygons must be calculated and represented tomographically for a grid on K_P.     

Hermite Interpolation of Solid Orientations with Circular Blending Quaternion Curves

Construction methods are presented that generate Hermite interpolation quaternion curves on SO(3). Two circular curves C₁(t) and C₂(t), 0 ≤ t ≤ 1, are generated that interpolate two orientations q₁ and q₂, and have boundary angular velocities: C₁′(0) = ω₁ and C₂′(1) = ω₂, respectively. They are smoothly blended together on SO(3) to generate a Hermite quaternion curve Q(t) ∈ SO(3), 0 ≤ t ≤ 1, which satisfies the boundary conditions: Q(0) = q₁, Q(1) = ₂, Q′(0) = ω₁, and Q′ (1) = ω₂.     

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.     

Linear closed-loop control in linear periodic systems with application to spin-stabilized bodies

A method is presented which solves the problem of determining the T-periodic feedback matrix K(t) of a linear periodic system (A(t), B(t) and C(t)), such that the closed-loop system has a desired stability property. The results are used to solve the problem of aligning the angular momentum and the spin axis of a spin-stabilized body with an inertial reference direction.     

Robust stabilisation of nonlinear plants via left coprime factorizations

In this paper we take steps towards the development of a robust stabilization theory for nonlinear plants. An approach using the left coprime factorizations of the plant and controller under certain differential boundedness assumptions is used. We first focus attention on a characterization of the class of all stabilizing nonlinear controllers K_Q for a nonlinear plant G, parameterized in terms of an arbitrary stable (nonlinear) operator Q. Also, we consider the dual class of all plants G_S stabilized by a given nonlinear controller K and parameterized in terms of an arbitrary stable (nonlinear) operator S. We show that a necessary and sufficient condition for K_Q to stabilize G_S with Q, S not necessarily stable, is that S stabilizes Q. This robust stabilization result is of interest for the solution of problems in the areas of nonlinear adaptive control and simultaneous stabilization. It specializes to known results for linear operators.     

Characterization of analytic phase signals

In many cases, a real-valued signal χ(t) may be associated with a complex-valued signal a(t)e^iθ(t), the analytic signal associated with χ(t) with the characteristic properties χ(t) = a(t) cosθ(t) and H(a(·)cosθ(·))(t) = a(t)sinθ(t). Using such obtained amplitude-frequency modulation the instantaneous frequency of χ(t) at the time t₀ may be defined to be θ′(t₀), provided θ′(t₀) ≥ 0. The purpose of this note is to characterize, in terms of analytic functions, the unimodular functions F(t) = C(t) + iS(t),C²(t) + S² (t) = 1, a.e., that satisfy HC(t) = S(t). This corresponds to the case a(t) ≡ 1 in the above formulation. We show that a unimodular function satisfies the required condition if and only if it is the boundary value of a so called inner function in the upper-half complex plane. We also give, through an explicit formula, a large class of functions of which the parametrization C(t) = cosθ(t) is available and the extra condition θ′(t) ≥ 0, a.e. is enjoyed. This class of functions contains Blaschke products in the upper-half complex plane as a proper subclass studied by Picinbono in [1].     

Continuous K-Nearest Neighbor Query for Moving Objects with Uncertain Velocity

One of the most important queries in spatio-temporal databases that aim at managing moving objects efficiently is the continuous K-nearest neighbor (CKNN) query. A CKNN query is to retrieve the K-nearest neighbors (KNNs) of a moving user at each time instant within a user-given time interval [t _s , t _e ]. In this paper, we investigate how to process a CKNN query efficiently. Different from the previous related works, our work relieves the past assumption, that an object moves with a fixed velocity, by allowing that the velocity of the object can vary within a known range. Due to the introduction of this uncertainty on the velocity of each object, processing a CKNN query becomes much more complicated. We will discuss the complications incurred by this uncertainty and propose a cost-effective P² KNN algorithm to find the objects that could be the KNNs at each time instant within the given query time interval. Besides, a probability-based model is designed to quantify the possibility of each object being one of the KNNs. Comprehensive experiments demonstrate the efficiency and the effectiveness of the proposed approach.

Stability radii of differential algebraic equations with structured perturbations

This paper deals with a formula for computing stability radii of a differential algebraic equation of the form AX^′(t)−BX(t)=0, where A,B are constant matrices. A computable formula for the complex stability radius is given and a key difference between the ordinary differential equation (ODEs for short) and the differential algebraic equation (DAEs for short) is pointed out. A special case where the real stability radius and the complex one are equal is considered.     

An Efficient Parallel Strategy for ComputingK-Terminal Reliability and Finding Most Vital Edges in 2-Trees and Partial 2-Trees

In this paper, we first develop a parallel algorithm for computingK-terminal reliability, denoted byR(G_K), in 2-trees. Based on this result, we can also computeR(G_K) in partial 2-trees using a method that transforms, in parallel, a given partial 2-tree into a 2-tree. Finally, we solve the problem of finding most vital edges with respect toK-terminal reliability in partial 2-trees. Our algorithms takeO(log n) time withC(m, n) processors on a CRCW PRAM, whereC(m, n) is the number of processors required to find the connected components of a graph withmedges andnvertices in logarithmic time.