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.     

A practicable approach to G biarc approximations for making accurate, smooth and non-gouged profile features in CNC contouring

Extensive research on G¹ biarc approximations to free-form curves has been conducted for the production of accurate, smooth and non-gouged profile features in CNC contouring. However, all the published work has only focused on improving the fitting accuracy between the biarc curve and the nominal free-form curve of a profile and minimizing the biarc number; as a result, the radii of the concave arcs of some biarcs could be less than the pre-determined tool radius, and the tool would overcut these arcs in machining, eventually gouging the profile. In this work, a new, practicable approach is proposed to completely solve this problem. The main feature of this approach is to find the gouging-free parameter interval of a biarc family, among which the radii of all the concave arcs are larger than the tool radius, and then to search in this interval for a best fitting biarc so that its approximation accuracy is within the tolerance. This approach is robust and easy to implement and can substantially promote the use of G¹ biarc curves for CNC machining.     

A simpler linear time 2/3−ε approximation for maximum weight matching

We present two approximation algorithms for the maximum weight matching problem that run in time . We give a simple and practical randomized algorithm and a somewhat more complicated deterministic algorithm. Both algorithms are exponentially faster in terms of ε than a recent algorithm by Drake and Hougardy. We also show that our algorithms can be generalized to find a 1−ε approximation to the maximum weight matching, for any ε>0.     

An approximation algorithm dependent on edge-coloring number for minimum maximal matching problem

We consider the minimum maximal matching problem, which is NP-hard (Yannakakis and Gavril (1980) [18]). Given an unweighted simple graph G=(V,E), the problem seeks to find a maximal matching of minimum cardinality. It was unknown whether there exists a non-trivial approximation algorithm whose approximation ratio is less than 2 for any simple graph. Recently, Z. Gotthilf et al. (2008) [5] presented a -approximation algorithm, where c is an arbitrary constant.In this paper, we present a -approximation algorithm based on an LP relaxation, where χ^′(G) is the edge-coloring number of G. Our algorithm is the first non-trivial approximation algorithm whose approximation ratio is independent of |V|. Moreover, it is known that the minimum maximal matching problem is equivalent to the edge dominating set problem. Therefore, the edge dominating set problem is also -approximable. From edge-coloring theory, the approximation ratio of our algorithm is , where Δ(G) represents the maximum degree of G. In our algorithm, an LP formulation for the edge dominating set problem is used. Fujito and Nagamochi (2002) [4] showed the integrality gap of the LP formulation for bipartite graphs is at least . Moreover, χ^′(G) is Δ(G) for bipartite graphs. Thus, as far as an approximation algorithm for the minimum maximal matching problem uses the LP formulation, we believe our result is the best possible.     

Finding shortest safari routes in simple polygons

Let P be a simple polygon, and let be a set of disjoint convex polygons inside P, each sharing one edge with P. The safari route problem asks for a shortest route inside P that visits each polygon in . In this paper, we first present a dynamic programming algorithm with running time O(n³) for computing the shortest safari route in the case that a starting point on the route is given, where n is the total number of vertices of P and polygons in . (Ntafos in [Comput. Geom. 1 (1992) 149-170] claimed a more efficient solution, but as shown in Appendix A of this paper, the time analysis of Ntafos' algorithm is erroneous and no time bound is guaranteed for his algorithm.) The restriction of giving a starting point is then removed by a brute-force algorithm, which requires O(n⁴) time. The solution of the safari route problem finds applications in watchman routes under limited visibility.     

A Flexible Approach to Bayesian Multiple Curve Fitting

We model sparse functional data from multiple subjects with a mixed-effects regression spline. In this model, the expected values for any subject (conditioned on the random effects) can be written as the sum of a population curve and a subject-specific deviate from this population curve. The population curve and the subject-specific deviates are both modeled as free-knot b-splines with k and k^′ knots located at and , respectively. To identify the number and location of the “free” knots, we sample from the posterior using reversible jump MCMC methods. Sampling from this posterior distribution is complicated, however, by the flexibility we allow for the model’s covariance structure. No restrictions (other than positive definiteness) are placed on the covariance parameters ψ and σ² and, as a result, no analytical form for the likelihood exists. In this paper, we consider two approximations to and then sample from the corresponding approximations to . We also sample from which has a likelihood that is available in closed form. While sampling from this larger posterior is less efficient, the resulting marginal distribution of knots is exact and allows us to evaluate the accuracy of each approximation. We then consider a real data set and explore the difference between and the more accurate approximation to .     

Efficient approximation algorithms for shortest cycles in undirected graphs

We describe a simple combinatorial approximation algorithm for finding a shortest (simple) cycle in an undirected graph. Given an adjacency-list representation of an undirected graph G with n vertices and unknown girth k, our algorithm returns with high probability a cycle of length at most 2k for even k and 2k+2 for odd k, in time . Thus, in general, it yields a approximation. For a weighted, undirected graph, with non-negative edge weights in the range {1,2,…,M}, we present a simple combinatorial 2-approximation algorithm for a minimum weight (simple) cycle that runs in time O(n²logn(logn+logM)).     

Very accurate posterior approximations based on finite mixtures of the hyperparameters conditionals

Consider a posterior density π(λ,φ) such that both and are known. We propose to approximate π(λ,φ) by , where is a finite mixture of the posterior conditionals . The weights and components of the mixture are chosen to minimize an approximate f-divergence between the approximate and the actual posterior. These approximate divergences are computed through an importance sampling idea using a simulated sample from the same finite mixture approximations. For the special case of the χ² or Harmonic divergences, once the minimum approximate divergences have been obtained, they can be plugged into total variation type inequalities to obtain precision limits for the corresponding approximations of posterior expectations of interest.When the algorithm can be used—namely, when both full conditionals and are known, it requires little computational, programming and diagnosing effort. Moreover, we present several examples which show that the approximations produced are extremely accurate, even when a small number of components are included in the mixture approximation.     

Improved deterministic approximation algorithms for Max TSP

We present an O(n³)-time approximation algorithm for the maximum traveling salesman problem whose approximation ratio is asymptotically , where n is the number of vertices in the input complete edge-weighted (undirected) graph. We also present an O(n³)-time approximation algorithm for the metric case of the problem whose approximation ratio is asymptotically . Both algorithms improve on the previous bests.     

Approximating weighted matchings in parallel

We present an NC approximation algorithm for the weighted matching problem in graphs with an approximation ratio of (1−ε). This improves the previously best approximation ratio of of an NC algorithm for this problem.     

The extension principle and a decomposition of fuzzy sets

We give an algorithm to decompose a fuzzy interval u. Using this decomposition and the multilinearization of a univariate function f, we obtain an approximation of the fuzzy interval , where is obtained from f by applying the extension principle. We provide approximation bounds. Some numeric illustration is provided.     

A new approximation algorithm for labeling points with circle pairs

We study the NP-hard problem of labeling points with maximum-radius circle pairs: given n point sites in the plane, find a placement for 2n interior-disjoint uniform circles, such that each site touches two circles and the circle radius is maximized. We present a new approximation algorithm for this problem that runs in time and O(n) space and achieves an approximation factor of (≈1.486+ε), which improves the previous best bound of 1.491+ε.     

The convergence of the geometric interpolation algorithm

The geometric interpolation algorithm is proposed by Maekawa et al. in [Maekawa T, Matsumoto Y, Namiki K. Interpolation by geometric algorithm. Computer-Aided Design 2007;39:313-23]. Without solving a system of equations, the algorithm generates a curve (surface) sequence, of which the limit curve (surface) interpolates the given data points. However, the convergence of the algorithm is a conjecture in the reference above, and demonstrated by lots of empirical examples. In this paper, we prove the conjecture given in the reference in theory, that is, the geometric interpolation algorithm is convergent for a blending curve (surface) with normalized totally positive basis, under the condition that the minimal eigenvalue of the collocation matrix D_k of the totally positive basis in each iteration satisfies . As a consequence, the geometric interpolation algorithm is convergent for Bézier, B-spline, rational Bézier, and NURBS curve (surface) if they satisfy the condition aforementioned, since Bernstein basis and B-spline basis are both normalized totally positive.     

The approximate swap and mismatch edit distance

There is no known algorithm that solves the general case of the approximate edit distance problem, where the edit operations are insertion, deletion, mismatch, and swap, in time o(nm), where n is the length of the text and m is the length of the pattern.In the effort to study this problem, the edit operations have been analyzed independently. Karloff [10] showed an algorithm that approximates the edit distance problem with only the mismatch operation in time . Amir et al. [4] showed that if the only edit operations allowed are swap and mismatch, then the exact edit distance problem can be solved in time .In this paper, we discuss the problem of approximate edit distance with swap and mismatch. We show a randomized time algorithm for the problem. The algorithm guarantees an approximation factor of (1+?) with probability of at least .     

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.