Biarc approximation of NURBS curves

An algorithm for approximating arbitrary NURBS curves with biarcs is presented. The main idea is to approximate the NURBS curve with a polygon, and then to approximate the polygon with biarcs to within the required tolerance. The method uses a parametric formulation of biarcs appropriate in geometric design using parametric curves. The method is most useful in numerical control to drive the cutter along straight line or circular paths.     

On approximation behavior of the greedy triangulation for convex polygons

We prove that the greedy triangulation heuristic for minimum weight triangulation of convex polygons yields solutions within a constant factor from the optimum. For interesting classes of convex polygons, we derive small upper bounds on the constant approximation factor. Our results contrast with Kirkpatrick's (n) bound on the approximation factor of the Delaunay triangulation heuristic for minimum weight triangulation of convexn-vertex polygons. On the other hand, we present a straightforward implementation of the greedy triangulation heuristic for ann-vertex convex point set or a convex polygon takingO(n ²) time andO(n) space. To derive the latter result, we show that given a convex polygonP, one can find for all verticesv ofP a shortest diagonal ofP incident tov in linear time. Finally, we observe that the greedy triangulation for convex polygons having so-called semicircular property can be constructed in timeO(n logn).     

A note on approximation of discrete data by G arc splines

Meek and Walton discussed the approximation of discrete data by G¹ arc splines in 1992. For a biarc from the start point A to the end point B, they assumed that the sum of two counterclockwise angles of the two arcs was equal to the sum of the counterclockwise angle from the start tangent vector to the vector B–A and that from the vector B–A to the terminal tangent vector. In this note, we show that the relation can be relaxed by the addition or subtraction of 2π.     

Semiparametric regression for assessing agreement using tolerance bands

This article describes a Bayesian semiparametric approach for assessing agreement between two methods for measuring a continuous variable using tolerance bands. A tolerance band quantifies the extent of agreement in methods as a function of a covariate by estimating the range of their differences in a specified large proportion of population. The mean function of differences is modelled using a penalized spline through its mixed model representation. The covariance matrix of the errors may also depend on a covariate. The Bayesian approach is straightforward to implement using the Markov chain Monte Carlo methodology. It provides an alternative to the rather ad hoc frequentist likelihood-based approaches that do not work well in general. Simulation for two commonly used models and their special cases suggests that the proposed Bayesian method has reasonably good frequentist coverage. Two real data sets are used for illustration, and the Bayesian and the frequentist inferences are compared.     

Error-bounded biarc approximation of planar curves

Presented in this paper is an error-bounded method for approximating a planar parametric curve with a G¹ arc spline made of biarcs. The approximated curve is not restricted in specially bounded shapes of confined degrees, and it does not have to be compatible with non-uniform rational B-splines (NURBS). The main idea of the method is to divide the curve of interest into smaller segments so that each segment can be approximated with a biarc within a specified tolerance. The biarc is obtained by polygonal approximation to the curve segment and single biarc fitting to the polygon. In this process, the Hausdorff distance is used as a criterion for approximation quality. An iterative approach is proposed for fitting an optimized biarc to a given polygon and its two end tangents. The approach is robust and acceptable in computation since the Hausdorff distance between a polygon and its fitted biarc can be computed directly and precisely. The method is simple in concept, provides reasonable accuracy control, and produces the smaller number of biarcs in the resulting arc spline. Some experimental results demonstrate its usefulness and quality.     

Discrete-time approximation of Wonhain filters

A continuous-rime finite-state Markov chain observed in white noise is considered. The well-known result of Wonham filter provides a formula for obtaining posterior probabilities. Although the filter is of finite dimension, numerical schemes are needed in applications because of the nonlinearity and because the observations are frequently collected in discrete moments. In this work, we develop approximation schemes of Wonham filters by constructing discrete-time recursive algorithms. We prove the convergence of the algorithm by weak convergence method and martingale averaging techniques. Numerical experiments are also famished to demonstrate the performance of our algorithms.     

Discrete-time approximation of Wonham filters

A continuous-time finite-state Markov chain observed in white noise is considered. The well-known result of Wonham filter provides a formula for obtaining posterior probabilities. Although the filter is of finite dimension, numerical schemes are needed in applications because of the nonlinearity and because the observations are frequently collected in discrete moments. In this work, we develop approximation schemes of Wonham filters by constructing discrete-time recursive algorithms. We prove the convergence of the algorithm by weak convergence method and martingale averaging techniques. Numerical experiments are also furnished to demonstrate the performance of our algorithms. This work was supported in part by the National Science Foundation.     

A note on the approximation of mean-payoff games

We consider the problem of designing approximation schemes for the values of mean-payoff games. It was recently shown that (1) mean-payoff with rational weights scaled on [−1,1]$[-1,1]$ admit additive fully-polynomial approximation schemes, and (2) mean-payoff games with positive weights admit relative fully-polynomial approximation schemes. We show that the problem of designing additive/relative approximation schemes for general mean-payoff games (i.e. with no constraint on their edge-weights) is P-time equivalent to determining their exact solution.     

Optimal arc spline approximation

We present a method for approximating a point sequence of input points by a G¹$G^1$-continuous (smooth) arc spline with the minimum number of segments while not exceeding a user-specified tolerance. Arc splines are curves composed of circular arcs and line segments (shortly: segments). For controlling the tolerance we follow a geometric approach: We consider a simple closed polygon P and two disjoint edges designated as the start s and the destination d. Then we compute a SMAP (smooth minimum arc path), i.e. a smooth arc spline running from s to d in P with the minimally possible number of segments. In this paper we focus on the mathematical characterization of possible solutions that enables a constructive approach leading to an efficient algorithm.     

Parameterized approximation of dominating set problems

A problem open for many years is whether there is an FPT algorithm that given a graph G and parameter k, either: (1) determines that G has no k-Dominating Set, or (2) produces a dominating set of size at most g(k), where g(k) is some fixed function of k. Such an outcome is termed an FPT approximation algorithm. We describe some results that begin to provide some answers. We show that there is no such FPT algorithm for g(k) of the form k+c (where c is a fixed constant, termed an additive FPT approximation), unless FPT=W[2]. We answer the analogous problem completely for the related Independent Dominating Set (IDS) problem, showing that IDS does not admit an FPT approximation algorithm, for any g(k), unless FPT=W[2].     

Multiterminal global routing: A deterministic approximation scheme

We consider the problem of routing multiterminal nets in a two-dimensional gate-array. Given a gate-array and a set of nets to be routed, we wish to find a routing that uses as little channel space as possible. We present a deterministic approximation algorithm that uses close to the minimum possible channel space. We cast the routing problem as a new form of zero-one multicommodity flow, an integer-programming problem. We solve this integer program approximately by first solving its linear-program relaxation and then rounding any fractions that appear in the solution to the linear program. The running time of the rounding algorithm is exponential in the number of terminals in a net but polynomial in the number of nets and the size of the array. The algorithm is thus best suited to cases where the number of terminals on each net is small.This work was done while the authors were with the Computer Science Division, University of California at Berkeley. The work of Prabhakar Raghavan was supported by an IBM Doctoral Fellowship, and the work of Clark Thompson was supported by a California State MICRO grant (AT&T Foundation).     

An approximation algorithm for sequential rectangle placement

We present a constant factor, polynomial time approximation algorithm for the problem of scheduling a sequence of rectangles on a matrix. The approximation is on the area covered by the rectangles, and a rectangle is placed on the matrix only if all its preceding rectangles in the sequence were already placed.     

On approximation algorithms for the terminal Steiner tree problem

The terminal Steiner tree problem is a special version of the Steiner tree problem, where a Steiner minimum tree has to be found in which all terminals are leaves. We prove that no polynomial time approximation algorithm for the terminal Steiner tree problem can achieve an approximation ratio less than (1−o(1))lnn unless NP has slightly superpolynomial time algorithms. Moreover, we present a polynomial time approximation algorithm for the metric version of this problem with a performance ratio of 2ρ, where ρ denotes the best known approximation ratio for the Steiner tree problem. This improves the previously best known approximation ratio for the metric terminal Steiner tree problem of ρ+2.     

On approximation behavior of the greedy triangulation for convex polygons

We prove that the greedy triangulation heuristic for minimum weight triangulation of convex polygons yields solutions within a constant factor from the optimum. For interesting classes of convex polygons, we derive small upper bounds on the constant approximation factor. Our results contrast with Kirkpatrick's Ω(n) bound on the approximation factor of the Delaunay triangulation heuristic for minimum weight triangulation of convexn-vertex polygons. On the other hand, we present a straightforward implementation of the greedy triangulation heuristic for ann-vertex convex point set or a convex polygon takingO(n ²) time andO(n) space. To derive the latter result, we show that given a convex polygonP, one can find for all verticesv ofP a shortest diagonal ofP incident tov in linear time. Finally, we observe that the greedy triangulation for convex polygons having so-called semicircular property can be constructed in timeO(n logn).     

An approximation by neural networkswith a fixed weight

Neural networks are widely used in many applications including astronomical physics,image processing, recognition, robotics, and automated target tracking, etc. Their ability to approximate arbitrary functions is the main reason for this popularity. In this paper, we discuss the constructive approximation on the whole real line by a neural networks with a sigmoidal activation function and a fixed weight. Using the convolution method, we show neural network approximation with a fixed weight to a continuous function on a compact interval. Also, we demonstrate a computational work that shows good agreement with theory.     

Asymptotic fully polynomial approximation schemes for variants of open-end bin packing

We consider three variants of the open-end bin packing problem. Such variants of bin packing allow the total size of items packed into a bin to exceed the capacity of a bin, provided that a removal of the last item assigned to a bin would bring the contents of the bin below the capacity. In the first variant, this last item is the minimum sized item in the bin, that is, each bin must satisfy the property that the removal of any item should bring the total size of items in the bin below 1. The next variant (which is also known as lazy bin covering is similar to the first one, but in addition to the first condition, all bins (expect for possibly one bin) must contain a total size of items of at least 1. We show that these two problems admit asymptotic fully polynomial time approximation schemes (AFPTAS). Moreover, they turn out to be equivalent. We briefly discuss a third variant, where the input items are totally ordered, and the removal of the maximum indexed item should bring the total size of items in the bin below 1, and show that this variant is strongly NP-hard.     

An improved approximation lower bound for finding almost stable maximum matchings

In the stable marriage problem that allows incomplete preference lists, all stable matchings for a given instance have the same size. However, if we ignore the stability, there can be larger matchings. Biró et al. defined the problem of finding a maximum cardinality matching that contains minimum number of blocking pairs. They proved that this problem is not approximable within some constant δ>1 unless P=NP, even when all preference lists are of length at most 3. In this paper, we improve this constant δ to n1−ε for any ε>0, where n is the number of men in an input.     

The minimization of axiom sets characterizing generalized approximation operators

In the axiomatic approach of rough set theory, rough approximation operators are characterized by a set of axioms that guarantees the existence of certain types of binary relations reproducing the operators. Thus axiomatic characterization of rough approximation operators is an important aspect in the study of rough set theory. In this paper, the independence of axioms of generalized crisp approximation operators is investigated, and their minimal sets of axioms are presented.