Extensions of the witness method to characterize under-, over- and well-constrained geometric constraint systems

This paper describes new ways to tackle several important problems encountered in geometric constraint solving, in the context of CAD, and which are linked to the handling of under- and over-constrained systems. It presents a powerful decomposition algorithm of such systems.Our methods are based on the witness principle whose theoretical background is recalled in a first step. A method to generate a witness is then explained. We show that having a witness can be used to incrementally detect over-constrainedness and thus to compute a well-constrained boundary system. An algorithm is introduced to check if anchoring a given subset of the coordinates brings the number of solutions to a finite number.An algorithm to efficiently identify all maximal well-constrained parts of a geometric constraint system is described. This allows us to design a powerful algorithm of decomposition, called W-decomposition, which is able to identify all well-constrained subsystems: it manages to decompose systems which were not decomposable by classic combinatorial methods.     

A surface blending approach for displacement features on freeform surfaces

Embedding a number of displacement features into a base surface is common in industrial product design and modeling, where displaced surface regions are blended with the unmodified surface region. The cubic Hermite interpolant is usually adopted for surface blending, in which tangent plane smoothness across the boundary curve is achieved. However, the polynomial degree of the tangent field curve obtained symbolically is considerably higher, and the reduction of the degree of a freeform curve is a non-trivial task. In this work, an approximation surface blending approach is proposed to achieve tangential continuity across the boundary curve. The boundary curve is first offset in the tangent field with the user-specified tolerance, after which it is refined to be compatible with the offset curve for surface blending. Since the boundary curve is offset in a three-dimensional (3D) space, the local self-intersection in the offset curve is addressed in a 2D space by approximately mapping the offset vectors in the respective tangent planes to the parameter space of the base surface. The proposed algorithm is validated using examples, and the normal vector deviation along the boundary curve is investigated.     

Localized construction of curved surfaces from polygon meshes: A simple and practical approach on GPU

We present a method for refining n-sided polygons on a given piecewise linear model by using local computation, where the curved polygons generated by our method interpolate the positions and normals of vertices on the input model. Firstly, we construct a Bézier curve for each silhouette edge. Secondly, we employ a new method to obtain C¹ continuous cross-tangent functions that are constructed on these silhouette curves. An important feature of our method is that the cross tangent functions are produced solely by their corresponding facet parameters. Gregory patches can therefore be locally constructed on every polygon while preserving G¹ continuity between neighboring patches. To provide a flexible shape control, several local schemes are provided to modify the cross-tangent functions so that the sharp features can be retained on the resultant models. Because of the localized construction, our method can be easily accelerated by graphics hardware and fully run on the Graphics Processing Unit (GPU).     

An iterative algorithm for homology computation on simplicial shapes

We propose a new iterative algorithm for computing the homology of arbitrary shapes discretized through simplicial complexes. We demonstrate how the simplicial homology of a shape can be effectively expressed in terms of the homology of its sub-components. The proposed algorithm retrieves the complete homological information of an input shape including the Betti numbers, the torsion coefficients and the representative homology generators.To the best of our knowledge, this is the first algorithm based on the constructive Mayer–Vietoris sequence, which relates the homology of a topological space to the homologies of its sub-spaces, i.e. the sub-components of the input shape and their intersections. We demonstrate the validity of our approach through a specific shape decomposition, based only on topological properties, which minimizes the size of the intersections between the sub-components and increases the efficiency of the algorithm.     

Global existence and nonexistence for degenerate parabolic equations with nonlinear boundary flux

In this paper, by constructing various kinds of sub- and super-solutions and using the basic properties of M-matrix, we give the necessary and sufficient conditions of global existence for nonnegative solutions to a degenerate parabolic system with completely coupled boundary conditions, which generalize the recent results of, for instance, Cui [Z. Cui, Critical curves of the non-Newtonian polytropic filtration equations coupled with nonlinear boundary conditions, Nonlinear Anal. 68 (2008) 3201–3208], Zhou–Mu [J. Zhou, C. Mu, Algebraic criteria for global existence or blow-up for a boundary coupled system of nonlinear diffusion equations, Appl. Anal. 86 (2007) 1185–1197] etc.     

Two-step extended RKN methods for oscillatory systems

In this paper, two-step extended Runge–Kutta–Nyström-type methods for the numerical integration of perturbed oscillators are presented and studied. The new methods inherit the framework of two-step hybrid methods and are adapted to the special feature of the true flows in both the internal stages and the updates. Based on the EN-trees theory [H.L. Yang, X.Y. Wu, X. You, Y.L. Fang, Extended RKN-type methods for numerical integration of perturbed oscillators, Comput. Phys. Comm. 180 (2009) 1777–1794], order conditions for the new methods are derived via the BBT-series defined on the set BT of branches and the BBWT-series defined on the subset BWT of BT. The stability and phase properties are analyzed. Numerical experiments show the applicability and efficiency of our new methods in comparison with the well-known high quality methods proposed in the scientific literature.     

Solving the Boltzmann equation on GPUs

We show how to accelerate the direct solution of the Boltzmann equation using Graphics Processing Units (GPUs). In order to fully exploit the computational power of the GPU, we choose a method of solution which combines a finite difference discretization of the free-streaming term with a Monte Carlo evaluation of the collision integral. The efficiency of the code is demonstrated by solving the two-dimensional driven cavity flow. Computational results show that it is possible to cut down the computing time of the sequential code of two order of magnitude. This makes the proposed method of solution a viable alternative to particle simulations for studying unsteady low Mach number flows.     

A high quality and small shadow size visual secret sharing scheme based on hybrid strategy for grayscale images

Many secret sharing schemes for digital images have been developed in recent decades. Traditional schemes typically must deal with the problem of computational complexity, and other visual secret sharing schemes come with a higher transmission cost and storage cost; that is, each shadow size is m times as big as the original secret image. The new (2,n) secret sharing scheme for grayscale images proposed in this paper is based a combination of acceptable image quality using block truncation coding (BTC), high compression ratio discrete wavelet transform (DWT) and good subjective performance of the vector quantization (VQ) technique. Experimental results confirm that our proposed scheme not only generates a high quality reconstructed original image but also generates small, random-like grayscale shadows.     

Real-time approximation of molecular interaction interfaces based on hierarchical space decomposition

The interaction interface between two molecules can be represented as a bisector surface equidistant from the two sets of spheres of varying radii representing atoms. We recursively divide a box containing both sphere-sets into uniform pairs of sub-boxes. The distance from each new box to each sphere-set is conservatively approximated by an interval, and the number of sphere-box computations is greatly reduced by pre-partitioning each sphere-set using a kd-tree. The subdivision terminates at a specified resolution, creating a box partition (BP) tree. A piecewise linear approximation of the bisector surface is then obtained by traversing the leaves of the BP tree and connecting points equidistant from the sphere-sets. In 124 experiments with up to 16,728 spheres, a bisector surface with a resolution of 1/2⁴ of the original bounding box was obtained in 28.8 ms on average.     

Output feedback design for saturated linear plants using deadzone loops

In this paper, we present an LMI-based synthesis approach on output feedback design for input saturated linear systems by using deadzone loops. Algorithms are developed for minimizing the upper bound on the regional L₂ gain for exogenous inputs with L₂ norm bounded by a given value, and for minimizing this upper bound with a guaranteed reachable set or domain of attraction. The proposed synthesis approach will always lead to regionally stabilizing controllers if the plant is exponentially unstable, to semi-global results if the plant is non-exponentially unstable, and to global results if the plant is already exponentially stable, where the only requirement on the linear plant is detectability and stabilizability. The effectiveness of the proposed techniques is illustrated with one example.     

Three results on frequency assignment in linear cellular networks

In the frequency assignment problem we are given a graph representing a wireless network and a sequence of requests, where each request is associated with a vertex. Each request has two more attributes: its arrival and departure times, and it is considered active from the time of arrival to the time of departure. We want to assign frequencies to all requests so that at each time step any two active requests associated with the same or adjacent vertices use different frequencies. The objective is to minimize the number of frequencies used.We focus exclusively on the special case of the problem when the underlying graph is a linear network (path). For this case, we consider both the offline and online versions of the problem, and we present three results. First, in the incremental online case, where the requests arrive over time, but never depart, we give an algorithm with an optimal (asymptotic) competitive ratio . Second, in the general online case, where the requests arrive and depart over time, we improve the current lower bound on the (asymptotic) competitive ratio to . Third, we prove that the offline version of this problem is NP-complete.     

Constrained curve fitting on manifolds

When designing curves on surfaces the need arises to approximate a given noisy target shape by a smooth fitting shape. We discuss the problem of fitting a B-spline curve to a point cloud by squared distance minimization in the case that both the point cloud and the fitting curve are constrained to lie on a smooth manifold. The on-manifold constraint is included by using the first fundamental form of the surface for squared distance computations between the point cloud and the fitting curve. For the solution we employ a constrained optimization algorithm that allows us to include further constraints such as one-sided fitting or surface regions that have to be avoided by the fitting curve. We illustrate the effectiveness of our algorithm by means of several examples showing different applications.     

Robust fault detection and isolation of time-delay systems using a geometric approach

This paper investigates the development of Fault Detection and Isolation (FDI) filters for both retarded and neutral time-delay systems with unknown time-varying delays. Using a geometric framework, the notion of a finite unobservability subspace is introduced for time-delay systems and an algorithm for its construction is presented. A bank of residual generators is then designed so that each residual is affected by one fault and is partially decoupled from the others while the H_∞ norm of the transfer function between the disturbances and the uncertainties in delays and the residuals are guaranteed to remain less than a prescribed value. Furthermore, it is shown that in the case of known delays it is possible to generate residuals that enjoy perfect decoupling properties among faults. Simulation results presented demonstrate the effectiveness of our proposed FDI algorithms.     

Stability of Cauchy–Jensen type functional equation in generalized fuzzy normed spaces

In this paper, we establish some stability results concerning the Cauchy–Jensen functional equation in generalized fuzzy normed spaces. The results of the present paper improve and extend some recent results.     

Solving model kinetic equations on GPUs

We present an algorithm specifically tailored for solving model kinetic equations onto Graphics Processing Units (GPUs). The efficiency of the algorithm is demonstrated by solving the one-dimensional shock wave structure problem and the two-dimensional low Mach number driven cavity flow. Computational results show that it is possible to cut down the computing time of the sequential codes of two order of magnitude. The algorithm can be easily extended to more general collision models.     

Hamiltonian connectivity and globally 3∗-connectivity of dual-cube extensive networks

In 2000, Li et al. introduced dual-cube networks, denoted by DC_n for n?1, using the hypercube family Q_n and showed the vertex symmetry and some fault-tolerant hamiltonian properties of DC_n. In this article, we introduce a new family of interconnection networks called dual-cube extensive networks, denoted by DCEN(G). Given any arbitrary graph G, DCEN(G) is generated from G using the similar structure of DC_n. We show that if G is a nonbipartite and hamiltonian connected graph, then DCEN(G) is hamiltonian connected. In addition, if G has the property that for any two distinct vertices u,v of G, there exist three disjoint paths between u and v such that these three paths span the graph G, then DCEN(G) preserves the same property. Furthermore, we prove that the similar results hold when G is a bipartite graph.     

A simple and efficient method for variable ranking according to their usefulness for learning

The selection of a subset of input variables is often based on the previous construction of a ranking to order the variables according to a given criterion of relevancy. The objective is then to linearize the search, estimating the quality of subsets containing the topmost ranked variables. An algorithm devised to rank input variables according to their usefulness in the context of a learning task is presented. This algorithm is the result of a combination of simple and classical techniques, like correlation and orthogonalization, which allow the construction of a fast algorithm that also deals explicitly with redundancy. Additionally, the proposed ranker is endowed with a simple polynomial expansion of the input variables to cope with nonlinear problems. The comparison with some state-of-the-art rankers showed that this combination of simple components is able to yield high-quality rankings of input variables. The experimental validation is made on a wide range of artificial data sets and the quality of the rankings is assessed using a ROC-inspired setting, to avoid biased estimations due to any particular learning algorithm.     

Learning to pour with a robot arm combining goal and shape learning for dynamic movement primitives

When describing robot motion with dynamic movement primitives (DMPs), goal (trajectory endpoint), shape and temporal scaling parameters are used. In reinforcement learning with DMPs, usually goals and temporal scaling parameters are predefined and only the weights for shaping a DMP are learned. Many tasks, however, exist where the best goal position is not a priori known, requiring to learn it. Thus, here we specifically address the question of how to simultaneously combine goal and shape parameter learning. This is a difficult problem because learning of both parameters could easily interfere in a destructive way. We apply value function approximation techniques for goal learning and direct policy search methods for shape learning. Specifically, we use “policy improvement with path integrals” and “natural actor critic” for the policy search. We solve a learning-to-pour-liquid task in simulations as well as using a Pa10 robot arm. Results for learning from scratch, learning initialized by human demonstration, as well as for modifying the tool for the learned DMPs are presented. We observe that the combination of goal and shape learning is stable and robust within large parameter regimes. Learning converges quickly even in the presence of disturbances, which makes this combined method suitable for robotic applications.     

Triangular bubble spline surfaces

We present a new method for generating a Gⁿ-surface from a triangular network of compatible surface strips. The compatible surface strips are given by a network of polynomial curves with an associated implicitly defined surface, which fulfill certain compatibility conditions. Our construction is based on a new concept, called bubble patches, to represent the single surface patches. The compatible surface strips provide a simple Gⁿ-condition between two neighboring bubble patches, which are used to construct surface patches, connected with Gⁿ-continuity. For n≤2, we describe the obtained Gⁿ-condition in detail. It can be generalized to any n≥3. The construction of a single surface patch is based on Gordon–Coons interpolation for triangles.Our method is a simple local construction scheme, which works uniformly for vertices of arbitrary valency. The resulting surface is a piecewise rational surface, which interpolates the given network of polynomial curves. Several examples of G⁰, G¹ and G²-surfaces are presented, which have been generated by using our method. The obtained surfaces are visualized with reflection lines to demonstrate the order of smoothness.     

Testing trivializing maps in the Hybrid Monte Carlo algorithm

We test a recent proposal to use approximate trivializing maps in a field theory to speed up Hybrid Monte Carlo simulations. Simulating the CPN−1 model, we find a small improvement with the leading order transformation, which is however compensated by the additional computational overhead. The scaling of the algorithm towards the continuum is not changed. In particular, the effect of the topological modes on the autocorrelation times is studied.