Incremental algorithm is one of the most popular procedures for constructing Delaunay triangulations （DTs）. However, the point insertion sequence has a great impact on the amount of work needed for the construction ...Incremental algorithm is one of the most popular procedures for constructing Delaunay triangulations （DTs）. However, the point insertion sequence has a great impact on the amount of work needed for the construction of DTs. It affects the time for both point location and structure update, and hence the overall computational time of the triangulation algorithm. In this paper, a simple deterministic insertion sequence is proposed based on the breadth-first-search on a Kd-tree with some minor modifications for better performance. Using parent nodes as search-hints, the proposed insertion sequence proves to be faster and more stable than the Hilbert curve order and biased randomized insertion order （BRIO）, especially for non-uniform point distributions over a wide range of benchmark examples.展开更多
A new geometric method to prove the total positivity of UE spline basis was proposed. UE spline basis is a kind of basis defined over algebraic-trigonometric unified space. UE spline basis shares most properties of th...A new geometric method to prove the total positivity of UE spline basis was proposed. UE spline basis is a kind of basis defined over algebraic-trigonometric unified space. UE spline basis shares most properties of the usual polynomial B-Splines. Total positivity is an important property for spline basis, it is highly related with shape preserving and variation diminishing properties. Knot inserted algorithm is the most useful algorithm for spline curves since many other useful properties are based on it. It is necessary to prove the total positivity of UE spline basis using knot inserted algorithm intuitively, not only enrich the UE spline basis theory, but also can be treated as supplement to the total positivity in algebraic sense. This approach also can be extended to other analogical bases.展开更多
基金supported by the National Natural Science Foundation of China (10972006 and 11172005)the National Basic Research Program of China (2010CB832701)
文摘Incremental algorithm is one of the most popular procedures for constructing Delaunay triangulations （DTs）. However, the point insertion sequence has a great impact on the amount of work needed for the construction of DTs. It affects the time for both point location and structure update, and hence the overall computational time of the triangulation algorithm. In this paper, a simple deterministic insertion sequence is proposed based on the breadth-first-search on a Kd-tree with some minor modifications for better performance. Using parent nodes as search-hints, the proposed insertion sequence proves to be faster and more stable than the Hilbert curve order and biased randomized insertion order （BRIO）, especially for non-uniform point distributions over a wide range of benchmark examples.
基金Supported by the National Science Foundation of China (60970079 and 60933008)
文摘A new geometric method to prove the total positivity of UE spline basis was proposed. UE spline basis is a kind of basis defined over algebraic-trigonometric unified space. UE spline basis shares most properties of the usual polynomial B-Splines. Total positivity is an important property for spline basis, it is highly related with shape preserving and variation diminishing properties. Knot inserted algorithm is the most useful algorithm for spline curves since many other useful properties are based on it. It is necessary to prove the total positivity of UE spline basis using knot inserted algorithm intuitively, not only enrich the UE spline basis theory, but also can be treated as supplement to the total positivity in algebraic sense. This approach also can be extended to other analogical bases.
