Approximate Bézier curves by cubic LN curves

In order to derive the offset curves by using cubic Bézier curves with a linear field of normal vectors (the so-called LN Bézier curves) more efficiently, three methods for approximating degree n Bézier curves by cubic LN Bézier curves are considered, which includes two traditional methods and one new method based on Hausdorff distance. The approximation based on shifting control points is equivalent to solving a quadratic equation, and the approximation based on L₂ norm is equivalent to solving a quartic equation. In addition, the sufficient and necessary condition of optimal approximation based on Hausdorff distance is presented, accordingly the algorithm for approximating the degree n Bézier curves based on Hausdorff distance is derived. Numerical examples show that the error of approximation based on Hausdorff distance is much smaller than that of approximation based on shifting control points and L₂ norm, furthermore, the algorithm based on Hausdorff distance is much simple and convenient.     

On the conditions for the coincidence of two cubic Bézier curves

In a recent article, Wang et al. [2] derive a necessary and sufficient condition for the coincidence of two cubic Bézier curves with non-collinear control points. The condition reads that their control points must be either coincident or in reverse order. We point out that this uniqueness of the control points for polynomial cubics is a straightforward consequence of a previous and more general result of Barry and Patterson, namely the uniqueness of the control points for rational Bézier curves. Moreover, this uniqueness applies to properly parameterized polynomial curves of arbitrary degree.     

Conditions for coincidence of two cubic Bézier curves

This paper presents a necessary and sufficient condition for judging whether two cubic Bézier curves are coincident: two cubic Bézier curves whose control points are not collinear are coincident if and only if their corresponding control points are coincident or one curve is the reversal of the other curve. However, this is not true for degree higher than 3. This paper provides a set of counterexamples of degree 4.     

Simultaneous approximation for Bézier variant of Szász-Mirakyan-Durrmeyer operators

We study the rate of convergence in simultaneous approximation for the Bézier variant of Szász-Mirakyan-Durrmeyer operators by using the decomposition technique of functions of bounded variation.     

Shape analysis of cubic trigonometric Bézier curves with a shape parameter

For the cubic trigonometric polynomial curves with a shape parameter (TB curves, for short), the effects of the shape parameter on the TB curve are made clear, the shape features of the TB curve are analyzed. The necessary and sufficient conditions are derived for these curves having single or double inflection points, a loop or a cusp, or be locally or globally convex. The results are summarized in a shape diagram of TB curves, which is useful when using TB curves for curve and surface modeling. Furthermore the influences of shape parameter on the shape diagram and the ability for adjusting the shape of the curve are shown by graph examples, respectively.     

Multi-degree reduction of tensor product Bézier surfaces with general boundary constraints

We propose an efficient approach to the problem of multi-degree reduction of rectangular Bézier patches, with prescribed boundary control points. We observe that the solution can be given in terms of constrained bivariate dual Bernstein polynomials. The complexity of the method is O(mn₁n₂) with m ? min(m₁, m₂), where (n₁, n₂) and (m₁, m₂) is the degree of the input and output Bézier surface, respectively. If the approximation—with appropriate boundary constraints—is performed for each patch of several smoothly joined rectangular Bézier surfaces, the result is a composite surface of global C^r continuity with a prescribed r ? 0. In the detailed discussion, we restrict ourselves to r ∈ {0, 1}, which is the most important case in practical application. Some illustrative examples are given.     

An approximate dynamic programming approach for the vehicle routing problem with stochastic demands

This paper examines approximate dynamic programming algorithms for the single-vehicle routing problem with stochastic demands from a dynamic or reoptimization perspective. The methods extend the rollout algorithm by implementing different base sequences (i.e. a priori solutions), look-ahead policies, and pruning schemes. The paper also considers computing the cost-to-go with Monte Carlo simulation in addition to direct approaches. The best new method found is a two-step lookahead rollout started with a stochastic base sequence. The routing cost is about 4.8% less than the one-step rollout algorithm started with a deterministic sequence. Results also show that Monte Carlo cost-to-go estimation reduces computation time 65% in large instances with little or no loss in solution quality. Moreover, the paper compares results to the perfect information case from solving exact a posteriori solutions for sampled vehicle routing problems. The confidence interval for the overall mean difference is (3.56%, 4.11%).     

A third order partial differential equation for isotropic boundary based triangular Bézier surface generation

We approach surface design by solving a linear third order Partial Differential Equation (PDE). We present an explicit polynomial solution method for triangular Bézier PDE surface generation characterized by a boundary configuration. The third order PDE comes from a symmetric operator defined here to overcome the anisotropy drawback of any operator over triangular Bézier surfaces.     

Accurate evaluation algorithm for bivariate polynomial in Bernstein–Bézier form

In this paper it is presented a compensated de Casteljau algorithm to accurately evaluate a bivariate polynomial in Bernstein–Bézier form. The principle is to apply error-free transformations to improve the traditional de Casteljau algorithm. A forward error and a running error analysis are performed. Finally, some numerical experiments illustrate the accuracy of the proposed algorithm in ill-conditioned problems.     

Iterative process for G-multi degree reduction of Bézier curves

In this paper, the issue of multi-degree reduction of Bézier curves with C¹ and G²-continuity at the end points of the curve is considered. An iterative method, which is the first of this type, is derived. It is shown that this algorithm converges and can be applied iteratively to get the required accuracy. Some examples and figures are given to demonstrate the efficiency of this method.     

On G continuous interpolatory composite quadratic Bézier curves

In the paper the interpolation by G² continuous composite quadratic Bézier curves is studied. It is shown that the interpolation problem can be naturally posed correctly in such a way that a smooth curve f is approximated up to the order 4, i.e., one order more than in the corresponding function case. In addition, the tangent direction of f is approximated up to order 3, and the curvature up to order 2.     

A note on iterative process for G-multi degree reduction of Bézier curves

In the paper [A. Rababah, S. Mann, Iterative process for G²-multi degree reduction of Bézier curves, Applied Mathematics and Computation 217 (2011) 8126-8133], Rababah and Mann proposed an iterative method for multi-degree reduction of Bézier curves with C¹ and G²-continuity at the endpoints. In this paper, we provide a theoretical proof for the existence of the unique solution in the first step of the iterative process, while the proof in their paper applies only in some special cases. Also, we give a complete convergence proof for the iterative method. We solve the problem by using convex quadratic optimization.     

Approximate dynamic programming for capacity allocation in the service industry

We consider a problem where different classes of customers can book different types of service in advance and the service company has to respond immediately to the booking request confirming or rejecting it. The objective of the service company is to maximize profit made of class-type specific revenues, refunds for cancellations or no-shows as well as cost of overtime. For the calculation of the latter, information on the underlying appointment schedule is required. In contrast to most models in the literature we assume that the service time of clients is stochastic and that clients might be unpunctual. Throughout the paper we will relate the problem to capacity allocation in radiology services. The problem is modeled as a continuous-time Markov decision process and solved using simulation-based approximate dynamic programming (ADP) combined with a discrete event simulation of the service period. We employ an adapted heuristic ADP algorithm from the literature and investigate on the benefits of applying ADP to this type of problem. First, we study a simplified problem with deterministic service times and punctual arrival of clients and compare the solution from the ADP algorithm to the optimal solution. We find that the heuristic ADP algorithm performs very well in terms of objective function value, solution time, and memory requirements. Second, we study the problem with stochastic service times and unpunctuality. It is then shown that the resulting policy constitutes a large improvement over an “optimal” policy that is deduced using restrictive, simplifying assumptions.     

Approximate dynamic programming algorithms for optimal dosage decisions in controlled ovarian hyperstimulation

In the controlled ovarian hyperstimulation (COH) treatment, clinicians monitor the patients’ physiological responses to gonadotropin administration to tradeoff between pregnancy probability and ovarian hyperstimulation syndrome (OHSS). We formulate the dosage control problem in the COH treatment as a stochastic dynamic program and design approximate dynamic programming (ADP) algorithms to overcome the well-known curses of dimensionality in Markov decision processes (MDP). Our numerical experiments indicate that the piecewise linear (PWL) approximation ADP algorithms can obtain policies that are very close to the one obtained by the MDP benchmark with significantly less solution time.     

An arc-exchange decomposition method for multistage dynamic networks with random arc capacities

Multistage dynamic networks with random arc capacities (MDNRAC) have been successfully used for modeling various resource allocation problems in the transportation area. However, solving these problems is generally computationally intensive, and there is still a need to develop more efficient solution approaches. In this paper, we propose a new heuristic approach that solves the MDNRAC problem by decomposing the network at each stage into a series of subproblems with tree structures. Each subproblem can be solved efficiently. The main advantage is that this approach provides an efficient computational device to handle the large-scale problem instances with fairly good solution quality. We show that the objective value obtained from this decomposition approach is an upper bound for that of the MDNRAC problem. Numerical results demonstrate that our proposed approach works very well.     

Approximating tensor product Bézier surfaces with tangent plane continuity

We present a simple method for degree reduction of tensor product Bézier surfaces with tangent plane continuity in L₂-norm. Continuity constraints at the four corners of surfaces are considered, so that the boundary curves preserve endpoints continuity of any order α. We obtain matrix representations for the control points of the degree reduced surfaces by the least-squares method. A simple optimization scheme that minimizes the perturbations of some related control points is proposed, and the surface patches after adjustment are C^∞ continuous in the interior and G¹ continuous at the common boundaries. We show that this scheme is applicable to surface patches defined on chessboard-like domains.     

Optimal policy for a dynamic,non-stationary,stochastic inventory problem with capacity commitment

This paper studies a single-product, dynamic, non-stationary, stochastic inventory problem with capacity commitment, in which a buyer purchases a fixed capacity from a supplier at the beginning of a planning horizon and the buyer’s total cumulative order quantity over the planning horizon is constrained with the capacity. The objective of the buyer is to choose the capacity at the beginning of the planning horizon and the order quantity in each period to minimize the expected total cost over the planning horizon. We characterize the structure of the minimum sum of the expected ordering, storage and shortage costs in a period and thereafter and the optimal ordering policy for a given capacity. Based on the structure, we identify conditions under which a myopic ordering policy is optimal and derive an equation for the optimal capacity commitment. We then use the optimal capacity and the myopic ordering policy to evaluate the effect of the various parameters on the minimum expected total cost over the planning horizon.