Constrained approximation of rational Bézier curves based on a matrix expression of its end points continuity condition

For high order interpolations at both end points of two rational Bézier curves, we introduce the concept of C^(v,u)-continuity and give a matrix expression of a necessary and sufficient condition for satisfying it. Then we propose three new algorithms, in a unified approach, for the degree reduction of Bézier curves, approximating rational Bézier curves by Bézier curves and the degree reduction of rational Bézier curves respectively; all are in L₂ norm and C^(v,u)-continuity is satisfied. The algorithms for the first and second problems can get the best approximation results, and for the third one, resorting to the steepest descent method in numerical optimization obtains a series of degree reduced curves iteratively with decreasing approximation errors. Compared to some well-known algorithms for the degree reduction of rational Bézier curves, such as the uniformizing weights algorithm, canceling the best linear common divisor algorithm and shifted Chebyshev polynomials algorithm, the new one presented here can give a better approximation error, do multiple degrees of reduction at a time and preserve high order interpolations at both end points.     

Kernel modeling for molecular surfaces using a uniform solution

In this paper, a rational Bézier surface is proposed as a uniform approach to modeling all three types of molecular surfaces (MS): the van der Waals surface (vdWS), solvent accessible surface (SAS) and solvent excluded surface (SES). Each molecular surface can be divided into molecular patches, which can be defined by their boundary arcs. The solution consists of three steps: topology modeling, boundary modeling and surface modeling. Firstly, using a weighted α-shape, topology modeling creates two networks to describe the neighboring relationship of the molecular atoms. Secondly, boundary modeling derives all boundary arcs from the networks. Thirdly, surface modeling constructs all three types of molecular surfaces patch-by-patch, based on the networks and the boundary arcs. For an SES, the singularity is specially treated to avoid self-intersections. Instead of approximation, this proposed solution can produce precise shapes of molecular surfaces. Since rational Bézier representation is much simpler than a trimmed non-uniform rational B-spline surface (NURBS), computational load can be significantly saved when dealing with molecular surfaces. It is also possible to utilize the hardware acceleration for tessellation and rendering of a rational Bézier surface. CAGD kernel modelers typically use NURBSs as a uniform representation to handle different types of free-form surface. This research indicates that rational Bézier representation, more specifically, a bi-cubic or 2×4 rational Bézier surface, is sufficient for kernel modeling of molecular surfaces and related applications.     

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

Curvature continuous offset approximation based on circle approximation using quadratic Bézier biarcs

We present a method for G² end-point interpolation of offset curves using rational Bézier curves. The method is based on a G² end-point interpolation of circular arcs using quadratic Bézier biarcs. We also prove the invariance of the Hausdorff distance between two compatible curves under convolution. Using this result, we obtain the exact Hausdorff distance between an offset curve and its approximation by our method. We present the approximation algorithm and give numerical examples.     

Finding the best conic approximation to the convolution curve of two compatible conics based on Hausdorff distance

We consider the convolution of two compatible conic segments. First, we find an exact parametric expression for the convolution curve, which is not rational in general, and then we find the conic approximation to the convolution curve with the minimum error. The error is expressed as a Hausdorff distance which measures the square of the maximal collinear normal distance between the approximation and the exact convolution curve. For this purpose, we identify the necessary and sufficient conditions for the conic approximation to have the minimum Haudorff distance from the convolution curve. Then we use an iterative process to generate a sequence of weights for the rational quadratic Bézier curves which we use to represent conic approximations. This sequence converges to the weight of the rational quadratic Bézier curve with the minimum Hausdorff distance, within a given tolerance. We verify our method with several examples.     

Multi-degree reduction of Bézier curves using reparameterization

L₂-norms are often used in the multi-degree reduction problem of Bézier curves or surfaces. Conventional methods on curve cases are to minimize , where and are the given curve and the approximation curve, respectively. A much better solution is to minimize , where is the closest point to point , that produces a similar effect as that of the Hausdorff distance. This paper uses a piecewise linear function L(t) instead of t to approximate the function φ(t) for a constrained multi-degree reduction of Bézier curves. Numerical examples show that this new reparameterization-based method has a much better approximation effect under Hausdorff distance than those of previous methods.     

Adaptive patch-based mesh fitting for reverse engineering

In this paper,  we propose a novel adaptive mesh fitting algorithm that fits a triangular model with G¹ smoothly stitching bi-quintic Bézier patches. Our algorithm first segments the input mesh into a set of quadrilateral patches, whose boundaries form a quadrangle mesh. For each boundary of each quadrilateral patch, we construct a normal curve and a boundary-fitting curve, which fit the normal and position of its boundary vertices respectively. By interpolating the normal and boundary-fitting curves of each quadrilateral patch with a Bézier patch, an initial G¹ smoothly stitching Bézier patches is generated. We perform this patch-based fitting scheme in an adaptive fashion by recursively subdividing the underlying quadrilateral into four sub-patches. The experimental results show that our algorithm achieves precision-ensured Bézier patches with G¹ continuity and meets the requirements of reverse engineering.     

Approximation capabilities of multilayer fuzzy neural networks on the set of fuzzy-valued functions

This paper first introduces a piecewise linear interpolation method for fuzzy-valued functions. Based on this, we present a concrete approximation procedure to show the capability of four-layer regular fuzzy neural networks to perform approximation on the set of all d_p continuous fuzzy-valued functions. This approach can also be used to approximate d_∞ continuous fuzzy-valued functions. An example is given to illustrate the approximation procedure.     

Cubic Bézier approximation of a digitized curve

In this paper we present an efficient technique for piecewise cubic Bézier approximation of digitized curve. An adaptive breakpoint detection method divides a digital curve into a number of segments and each segment is approximated by a cubic Bézier curve so that the approximation error is minimized. Initial approximated Bézier control points for each of the segments are obtained by interpolation technique i.e. by the reverse recursion of De Castaljau's algorithm. Two methods, two-dimensional logarithmic search algorithm (TDLSA) and an evolutionary search algorithm (ESA), are introduced to find the best-fit Bézier control points from the approximate interpolated control points. ESA based refinement is proved to be better experimentally. Experimental results show that Bézier approximation of a digitized curve is much more accurate and uses less number of points compared to other approximation techniques.     

Data reduction of large vector graphics

Fast algorithm for joint near-optimal approximation of multiple polygonal curves is proposed. It is based on iterative reduced search dynamic programming introduced earlier for the min-εproblem of a single polygonal curve. The proposed algorithm jointly optimizes the number of line segments allocated to the different individual curves, and the approximation of the curves by the given number of segments. Trade-off between time and optimality is controlled by the breadth of the search, and by the numbers of iterations applied.     

On global solutions to fractional functional differential equations with infinite delay in Fréchet spaces

In this paper, we investigate global uniqueness results for fractional functional differential equations with infinite delay in Fréchet spaces. We shall rely on a nonlinear alternative of Leray-Schauder type in Fréchet spaces due to Frigon and Granas. The results are obtained by using the α-resolvent family (S_α(t))_t≥0 on a complex Banach space X combined with the above-mentioned fixed point theorem. As an application, a controllability result with one parameter is also provided to illustrate the theory.     

An approximation of circular arcs by quartic Bézier curves

In this paper we propose an approximation method for circular arcs by quartic Bézier curves. Using an alternative error function, we give the closed form of the Hausdorff distance between the circular arc and the quartic Bézier curve. We also show that the approximation order is eight. By subdivision of circular arcs with equi-length, our method yields the curvature continuous spline approximation of the circular arc. We confirm that the approximation proposed in this paper has a smaller error than previous quartic Bézier approximations.     

Cubic structures applied to ideals of BCI-algebras

The notions of cubic a-ideals and cubic p-ideals are introduced, and several related properties are investigated. Characterizations of a cubic a-ideal are established. Relations between cubic p-ideals, cubic a-ideals and cubic q-ideals are discussed. The cubic extension property of a cubic a-ideal is discussed.     

Two-machine flow-shop scheduling with rejection

We study a scheduling problem with rejection on a set of two machines in a flow-shop scheduling system. We evaluate the quality of a solution by two criteria: the first is the makespan and the second is the total rejection cost. We show that the problem of minimizing the makespan plus total rejection cost is NP-hard and for its solution we provide two different approximation algorithms, a pseudo-polynomial time optimization algorithm and a fully polynomial time approximation scheme (FPTAS). We also study the problem of finding the entire set of Pareto-optimal points (this problem is NP-hard due to the NP-hardness of the same problem variation on a single machine [20]). We show that this problem can be solved in pseudo-polynomial time. Moreover, we show how we can provide an FPTAS that, given that there exists a Pareto optimal schedule with a total rejection cost of at most R and a makespan of at most K, finds a solution with a total rejection cost of at most (1+?)R and a makespan value of at most (1+?)K. This is done by defining a set of auxiliary problems and providing an FPTAS algorithm to each one of them.     

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.     

Verification of reactive systems via instantiation of Parameterised Boolean Equation Systems

Verification problems for finite- and infinite-state processes, like model checking and equivalence checking, can effectively be encoded in Parameterised Boolean Equation Systems (PBESs). Solving the PBES then solves the encoded problem. The decidability of solving a PBES depends on the data sorts that occur in the PBES. We describe a pragmatic methodology for solving PBESs, viz., by attempting to instantiate them to the sub-fragment of Boolean Equation Systems (BESs). Unlike solving PBESs, solving BESs is a decidable problem. Based on instantiation, verification using PBESs can effectively be done fully automatically in most practical cases. We demonstrate this by solving several complex verification problems using a prototype implementation of our instantiation technique. In addition, practical issues concerning this implementation are addressed. Furthermore, we illustrate the effectiveness of instantiation as a transformation on PBESs when solving verification problems involving systems of infinite size.     

A vertex-first parametric algorithm for polyhedron blending

This paper enhances the conventional parametric algorithms for polyhedron blending, by strategically inverting the edges-first approach to vertex-first, so that matching the vertex blending surface (using a triangular or tensor product Bézier surface, or an S-patch) with the edge blending surfaces (generated by Hartmann method) becomes essentially easier. Based on a study of cross boundary derivatives (those of S-patches are deduced herein), G^g-continuity between all the above surfaces and the primary planar faces is achieved by a novel trick as a first step: assigning the vertex, some edge points and some face points to be the proper control points. This still leaves enough free parameters usable for changing the blending configuration. The new algorithm is illustrated with two practical examples involving miscellaneous vertices up to 6-edge convex–concave.