A DP curve is a new kind of parametric curve defined by Delgado and Peña (2003); it has very good properties when used in both geometry and algebra, i.e., it is shape preserving and has a linear time complexity for evaluation. It overcomes the disadvantage of some generalized Ball curves that are fast for evaluation but cannot preserve shape, and the disadvantage of the Bézier curve that is shape preserving but slow for evaluation. It also has potential applications in computer-aided design and manufacturing (CAD/CAM) systems. As conic section is often used in shape design, this paper deduces the necessary and sufficient conditions for rational cubic or quartic DP representation of conics to expand the application area of DP curves. The main idea is based on the transformation relationship between low degree DP basis and Bernstein basis, and the representation theory of conics in rational low degree Bézier form. The results can identify whether a rational low degree DP curve is a conic section and also express a given conic section in rational low degree DP form, i.e., give positions of the control points and values of the weights of rational cubic or quartic DP conics. Finally, several numerical examples are presented to validate the effectiveness of the method.

The computation of geodesic distances or paths between two points on triangulated meshes is a common operation in many computer graphics applications. In this article, we present an exact algorithm for the single-source all-vertices shortest path problem. Mitchell et al. [1987] proposed an O ( n 2 log n ) method (MMP), based on Dijkstra's algorithm, where n is the complexity of the polyhedral surface. Then, Chen and Han [1990] (CH) improved the running time to O ( n 2 ). Interestingly Surazhsky et al. [2005] provided experimental evidence demonstrating that the MMP algorithm runs many times faster, in practice, than the CH algorithm. The CH algorithm encodes the structure of the set of shortest paths using a set of windows on the edges of the polyhedron. Our experiments showed that in many examples over 99% of the windows created by the CH algorithm are of no use to define a shortest path. So this article proposes to improve the CH algorithm by two separate techniques. One is to filter out useless windows using the current estimates of the distances to the vertices, the other is to maintain a priority queue like that achieved in Dijkstra's algorithm. Our experimental results suggest that the improved CH algorithm, in spite of an O ( n 2 log n ) asymptotic time complexity, greatly outperforms the original CH algorithm in both time and space. Furthermore, it generally runs faster than the MMP algorithm and uses considerably less space.

This paper studies the multi-degree reduction of tensor product Bézier surfaces with any degree interpolation conditions of four corners, which is urgently to be resolved in many CAD/CAM systems. For the given conditions of corners interpolation, this paper presents one intuitive method of degree reduction of parametric surfaces. Another new approximation algorithm of multi-degree reduction is also presented with the degree elevation of surfaces and the Chebyshev polynomial approximation theory. It obtains the good approximate effect and the boundaries of degree reduced surface can preserve the prescribed continuities. The degree reduction error of the latter algorithm is much smaller than that of the first algorithm. The error bounds of degree reduction of two algorithms are also presented.