Spline approximation of offset curves

This paper deals with the approximation of (regular) offset curves (of a given spline curve of degree n) by a spline curve of arbitrarily chosen degree m. The approximating spline curves are determined by geometric continuity conditions and by parameter optimization for minimizing the range of the approximation error.     

A Direct Approach to Computing theμ-basis of Planar Rational Curves

This paper presents an O(n²) algorithm, based on Gröbner basis techniques, to compute the μ -basis of a degree n planar rational curve. The prior method involved solving a set of linear equations whose complexity by standard numerical methods was O(n³). The μ -basis is useful in computing the implicit equation of a parametric curve and can express the implicit equation in the form of a determinant that is smaller than that obtained by taking the resultant of the parametric equations.     

对可调控Bézier曲线的改进

目的 在用Bézier曲线表示复杂形状时,相邻曲线的控制顶点间必须满足一定的光滑性条件。一般情况下,对光滑度的要求越高,条件越复杂。通过改进文献中的“可调控Bézier曲线”,以构造具有多种优点的自动光滑分段组合曲线。方法 首先给出了两条位置连续的曲线G^l连续的一个充分条件,进而证明了“可调控Bézier曲线”在普通Bézier曲线的G^l光滑拼接条件下可达G^l(l为曲线中的参数)光滑拼接。然后对“可调控Bézier基”进行改进得到了一组新的基函数,利用该基函数按照Bézier曲线的定义方式构造了一种新曲线。分析了该曲线的光滑拼接条件,并根据该条件定义了一种分段组合曲线。结果 对于新曲线而言,只要前一条曲线的最后一条控制边与后一条曲线的第1条控制边重合,两条曲线便自动光滑连接,并且在连接点处的光滑度可以简单地通过改变参数的值来自由调整。由新曲线按照特殊方式构成的分段组合曲线具有类似于B样条曲线的自动光滑性和局部控制性。不同的是,组合曲线的各条曲线段可以由不同数量的控制顶点定义,选择合适的参数,可以使曲线在各个连接点处达到任何期望的光滑度。另外,改变一个控制顶点,至多只会影响两条曲线段的形状,改变一条曲线段中的参数,只会影响当前曲线段的形状,以及至多两个连接点处的光滑度。结论 本文给出了构造易于拼接的曲线的通用方法,极大简化了曲线的拼接条件。此基础上,提出的一种新的分段组合曲线定义方法,无需对控制顶点附加任何条件,所得曲线自动光滑,且其形状、光滑度可以或整体或局部地进行调整。本文方法具有一般性,为复杂曲线的设计创造了条件。     

Motion synthesis with decoupled parameterization

In real-time animation systems, motion interpolation techniques are widely used for their controllability and efficiency. The techniques sample the parameter space using example motions, and interpolate them to compute the blend weights corresponding to the given parameters. A main problem of the techniques is that, as the dimension n of the parameter space increases, the number of required example motions increases exponentially, i.e. O(c ⁿ ). To resolve the problem, this paper proposes to use two decoupled parameter spaces for controlling the upper body and the lower body separately. At each frame time, a parameterized motion space produces a source frame, and the target frame is synthesized by splicing the upper body of one source frame with the lower body of the other. In order to have the two source frames correlated with each other, a time-warping scheme has been developed. Furthermore, in order to handle the dynamic properties of the parameter samples of the upper body, we have developed an approximation technique for quickly determining the sample positions in its parameter space. This decoupled parameterization method alleviates the complexity problem, e.g. from O(c ⁶) to O(c ³), while providing the users with the capability of convenient control over the character.     

On Approximating Polygonal Curves in Two and Three Dimensions

Given a polygonal curve P =[p₁, p₂, . . . , p_n], the polygonal approximation problem considered calls for determining a new curve P′ = [p′₁, p′₂, . . . , p′_m] such that (i) m is significantly smaller than n, (ii) the vertices of P′ are an ordered subset of the vertices of P, and (iii) any line segment [p′_A, p′_{A + 1} of P′ that substitutes a chain [p_B, . . . , p_C] in P is such that for all i where B ≤ i ≤ C, the approximation error of p_i with respect to [p′_A, p′_{A + 1}], according to some specified criterion and metric, is less than a predetermined error tolerance. Using the parallel-strip error criterion, we study the following problems for a curve P in R^d, where d = 2, 3: (i) minimize m for a given error tolerance and (ii) given m, find the curve P′ that has the minimum approximation error over all curves that have at most m vertices. These problems are called the min-# and min-ϵ problems, respectively. For R² and with any one of the L₁, L₂, or L_∞ distance metrics, we give algorithms to solve the min-# problem in O(n²) time and the min-ϵ problem in O(n² log n) time, improving the best known algorithms to date by a factor of log n. When P is a polygonal curve in R³ that is strictly monotone with respect to one of the three axes, we show that if the L₁ and L_∞ metrics are used then the min-# problem can be solved in O(n²) time and the min-ϵ problem can be solved in O(n³) time. If distances are computed using the L₂ metric then the min-# and min-ϵ problems can be solved in O(n³) and O(n³ log n) time, respectively. All of our algorithms exhibit O(n²) space complexity. Finally, we show that if it is not essential to minimize m, simple modifications of our algorithms afford a reduction by a factor of n for both time and space.     

Some remarks on Bézier curves

Parametric polynomial curves in Bézier-Bernstein representation are considered as prohections of rational norm curves of degree n in n-space; from this point of view the singularities of a planar Bézier cubic are determined and expressed by its affine invariants. Secondly, for an arbitrary pair of adjacent parametric curves in homogeneous coordinates, the general conditions for geometric continuity of any order k, G^k, are established.This result generalizes the corresponding conditions in the non-homogeneous (affine) case, recently obtained by [Goodman '84]. Some applications are given for Bézier curves. In particular, for γ-splines [Boehm '85], the existence of a global rational parameter that makes it to a C² parametric curve is shown. Furthermore, for two adjacent rational Bézier curves the complete conditions for G³ are stated using the projective properties of the control points only.     

Strong computational lower bounds via parameterized complexity

We develop new techniques for deriving strong computational lower bounds for a class of well-known NP-hard problems. This class includes weighted satisfiability, dominating set, hitting set, set cover, clique, and independent set. For example, although a trivial enumeration can easily test in time O(nk) if a given graph of n vertices has a clique of size k, we prove that unless an unlikely collapse occurs in parameterized complexity theory, the problem is not solvable in time f(k)no(k) for any function f, even if we restrict the parameter values to be bounded by an arbitrarily small function of n. Under the same assumption, we prove that even if we restrict the parameter values k to be of the order Θ(μ(n)) for any reasonable function μ, no algorithm of running time no(k) can test if a graph of n vertices has a clique of size k. Similar strong lower bounds on the computational complexity are also derived for other NP-hard problems in the above class. Our techniques can be further extended to derive computational lower bounds on polynomial time approximation schemes for NP-hard optimization problems. For example, we prove that the NP-hard distinguishing substring selection problem, for which a polynomial time approximation scheme has been recently developed, has no polynomial time approximation schemes of running time f(1/?)no(1/?) for any function f unless an unlikely collapse occurs in parameterized complexity theory.     

Quadratic approximation to plane parametric curves and its application in approximate implicitization

Expressing complex curves with simple parametric curve segments is widely used in computer graphics, CAD and so on. This paper applies rational quadratic B-spline curves to give a global C ¹ continuous approximation to a large class of plane parametric curves including rational parametric curves. Its application in approximate implicitization is also explored. The approximated parametric curve is first divided into intrinsic triangle convex segments which can be efficiently approximated with rational quadratic Bézier curves. With this approximation, we keep the convexity and the cusp (sharp) points of the approximated curve with simple computations. High accuracy approximation is achieved with a small number of quadratic segments. Experimental results are given to demonstrate the operation and efficiency of the algorithm.     

Fuzzy Information On Discrete And Continuous Domains: Approximation Results

Measures of information based on fuzzy sets have been defined both for finite and for continuous universes. In the continuous case, the measure of information I(f) depends on the concept of non-increasing rearrangement of the function f. It has been observed that I(f) can be obtained as a limit of discrete distributions π^(N) approximating f. We consider the approximation problem in more detail, and study the convergence of I(π^(N)) to I(f) in terms of the smoothness properties of f itself (modulus of continuity and Lipschitz exponent).     

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

Fast computation of smallest enclosing circle with center on a query line segment

Here we propose an efficient algorithm for computing the smallest enclosing circle whose center is constrained to lie on a query line segment. Our algorithm preprocesses a given set of n points P={p₁,p₂,…,pn} such that for any query line or line segment L, it efficiently locates a point c on L that minimizes the maximum distance among the points in P from c. Roy et al. [S. Roy, A. Karmakar, S. Das, S.C. Nandy, Constrained minimum enclosing circle with center on a query line segment, in: Proc. of the 31st Mathematical Foundation of Computer Science, 2006, pp. 765-776] have proposed an algorithm that solves the query problem in O(log²n) time using O(nlogn) preprocessing time and O(n) space. Our algorithm improves the query time to O(logn); but the preprocessing time and space complexities are both O(n²).     

Visibility of disjoint polygons

Consider a collection of disjoint polygons in the plane containing a total ofn edges. We show how to build, inO(n ²) time and space, a data structure from which inO(n) time we can compute the visibility polygon of a given point with respect to the polygon collection. As an application of this structure, the visibility graph of the given polygons can be constructed inO(n ²) time and space. This implies that the shortest path that connects two points in the plane and avoids the polygons in our collection can be computed inO(n ²) time, improving earlierO(n ² logn) results.     

A bucketing algorithm for the orthogonal segment intersection search problem and its practical efficiency

The orthogonal segment intersection search problem is stated as follows: given a setS ofn orthogonal segments in the plane, report all the segments ofS that intersect a given orthogonal query segment. For this problem, we propose a simple and practical algorithm based on bucketing techniques. It constructs, inO(n) time preprocessing, a search structure of sizeO(n) so that all the segments ofS intersecting a query segment can be reported inO(k) time in the average case, wherek is the number of the reported segments. The proposed algorithm as well as existing algorithms is implemented in FORTRAN, and their practical efficiencies are investigated through computational experiments. It is shown that ourO(k) search time,O(n) space, andO(n) preprocessing time algorithm is in practice the most efficient among the algorithms tested.     

高阶连续的形状可调三角多项式曲线曲面

目的目前使用的B样条曲线曲面存在着高连续阶与高局部调整性两者无法兼而有之的不足,且B样条曲线曲面的形状被控制顶点和节点向量唯一确定,这些因素影响着B样条方法的几何设计效果与方便性。本文旨在克服这种局限,以期构造具有高次B样条方法的高连续阶,低次B样条方法的高局部调整性,以及有理B样条方法权因子决定的形状调整性的曲线曲面。方法在三角函数空间上构造了一组含参数的调配函数,进而定义具有与3次B样条曲线曲面相同结构的新曲线与张量积曲面。结果新曲线曲面继承了B样条方法的凸包性、对称性、几何不变性等诸多性质。不同的是,同样是基于4点分段,3次均匀B样条曲线C2连续,而对于等距节点,在一般情况下,新曲线C5连续,当参数取特殊值时可达C7连续。新曲线在C5连续的情况下存在1个形状参数,能较好地调整曲线的形状同时又无须改变控制顶点。另外,将形状参数设为特定值,新曲线可以自动插值给定点列。新曲面具有与新曲线相应的优点。结论在强局部性下实现高阶连续性的形状可调分段组合曲线曲面,为高阶光滑曲线曲面的设计提供了可能,并且新曲线实现了逼近与插值的统一表示,能较好地应用于工程实际。调配函数的构造方法具有一般性,可用相同方式构造其他具有类似性质的调配函数。     

Parametric G n blending of curves and surfaces

We introduce a simple blending method for parametric curves and surfaces that produces families of parametrically defined, G ⁿ –continuous blending curves and surfaces. The method depends essentially on the parameterizations of the curves/surfaces to be blended. Hence, the flexibility of the method relies on the existence of suitable parameter transformations of the given curves/surfaces. The feasibility of the blending method is shown by several examples. The shape of the blend curve/surface can be changed in a predictable way with the aid of two design parameters (thumb weight and balance).     

Exponential-time approximation of weighted set cover

The Set Cover problem belongs to a group of hard problems which are neither approximable in polynomial time (at least with a constant factor) nor fixed parameter tractable, under widely believed complexity assumptions. In recent years, many researchers design exact exponential-time algorithms for problems of that kind. The goal is getting the time complexity still of order O(cn), but with the constant c as small as possible. In this work we extend this line of research and we investigate whether the constant c can be made even smaller when one allows constant factor approximation.In fact, we describe a kind of approximation schemes—trade-offs between approximation factor and the time complexity. We use general transformations from exponential-time exact algorithms to approximations that are faster but still exponential-time. For example, we show that for any reduction rate r, one can transform any O^∗(cn)-time¹ algorithm for Set Cover into a (1+lnr)-approximation algorithm running in time O^∗(cn/r). We believe that results of that kind extend the applicability of exact algorithms for NP-hard problems.     

A hierarchical structure for surface approximation

Hierarchical triangulation is a method for point selection and surface representation where the surface is approximated at successively finer levels of detail by triangular patches whose projections in the horizontal plane are nested. A tree data structure for this representation can be constructed in O(n²) worst case and O(n log n) average case time, where n is the number of data points considered. Efficient algorithms for approximation of the elevation of an arbitrary point, contour extraction, and conversion of the hierarchical structure into an ordinary triangulated irregular network, are demonstrated. The convergence and the optimality of the approximation and the relationship of the hierarchical triangulation to a structured graph representation are examined.     

Computing shortest transversals

We present anO(nlog² n) time andO(n) space algorithm for computing the shortest line segment that intersects a set ofn given line segments or lines in the plane. If the line segments do not intersect the algorithm may be trimmed to run inO(nlogn) time. Furthermore, in combination with linear programming the algorithm will also find the shortest line segment that intersects a set ofn isothetic rectangles in the plane inO(nlogk) time, wherek is the combinatorial complexity of the space of transversals andk≤4n. These results find application in: (1) line-fitting between a set ofn data ranges where it is desired to obtain the shortestline-of-fit, (2) finding the shortest line segment from which a convexn-vertex polygon is weakly externally visible, and (3) determing the shortestline-of-sight between two edges of a simplen-vertex polygon, for whichO(n) time algorithms are also given. All the algorithms are based on the solution to a new fundamental geometric optimization problem that is of independent interest and should find application in different contexts as well.     

A Study of Permutation Networks: New Designs and Some Generalizations

Permutation networks have been used in the literature to model interprocessor and processor-memory interconnections in parallel computers. This paper introduces new permutation network designs and generalizes the notion of a permutation network to provide a more flexible model of such interconnections. The new designs are based concentrators and superconcentrators, and for n inputs they can be optimized to obtain self-routing permutation networks with O(n lg n) cost, O(lg n) depth, and O(lg²n) routing time. The main feature of these new network designs is that they do not require complex routing schemes such as Clos networks since they are inherently self-routing. Generalizations of these designs are also given to obtain permutation networks in which the numbers of inputs and outputs may be different, and/or the maximum number of parallel routes between inputs and outputs can be less than the number of inputs or outputs, or both. For n inputs, αn outputs, and O(n^ϵ) parallel routes, where 0 < α ≤ 1, 0 < ϵ < 1, these generalized designs can be optimized to have permutation networks with O(n) cost, O(lg n), depth, and O(lg²n) routing time. It is shown that the previously known designs, such as Clos networks, result in inferior realizations when compared with these new designs.