Fast Range Searching with Delaunay Triangulations

This paper studies the idea of answering range searching queries using simple data structures. The only data structure we need is the Delaunay Triangulation of the input points. The idea is to first locate a vertex of the (arbitrary) query polygon and walk along the boundary of the polygon in the Delaunay Triangulation and report all the points enclosed by the query polygon. For a set of uniformly distributed random points in 2-D and a query polygon the expected query time of this algorithm is O(n ^1/3 + Q + E K + L _r n ^1/2), where Q is the size of the query polygon , {\bf E}K = O(n\bcdot area is the expected number of output points, L _r is a parameter related to the shape of the query polygon and n, and L _r is always bounded by the sum of the edge lengths of . Theoretically, when L _r = O(1/n^1/6) the expected query time is O(n^1/3 + Q + E K), which improves the best known average query time for general range searching. Besides the theoretical meaning, the good property of this algorithm is that once the Delaunay Triangulation is given, no additional preprocessing is needed. In order to obtain empirical results, we design a new algorithm for generating random simple polygons within a given domain. Our empirical results show that the constant coefficient of the algorithm is small, at least for the special (practical) cases when the query polygon is either a triangle (simplex range searching) or an axis-parallel box (orthogonal range searching) and for the general case when the query polygons are generated by our new polygon-generating algorithms and their sizes are relatively small.     

Efficient mesh optimization schemes based on Optimal Delaunay Triangulations

In this paper, several mesh optimization schemes based on Optimal Delaunay Triangulations are developed. High-quality meshes are obtained by minimizing the interpolation error in the weighted L¹ norm. Our schemes are divided into classes of local and global schemes. For local schemes, several old and new schemes, known as mesh smoothing, are derived from our approach. For global schemes, a graph Laplacian is used in a modified Newton iteration to speed up the local approach. Our work provides a mathematical foundation for a number of mesh smoothing schemes often used in practice, and leads to a new global mesh optimization scheme. Numerical experiments indicate that our methods can produce well-shaped triangulations in a robust and efficient way.     

基于非结构三角网格的两种自适应技术研究

实现两种基于无结构Delaunay三角网格的自适应方法，并且把两种方法分别应用于求解一个典型的二维溃坝问题，同时对两种方法的数值结果和稳定性进行比较。数值结果表明两种方法对提高数值解的精度和调整问题求解区域的剖分起到明显的作用。     

基于非结构三角网格的两种自适应技术研究

实现两种基于无结构Delaunay三角网格的自适应方法,并且把两种方法分别应用于求解一个典型的二维溃坝问题,同时对两种方法的数值结果和稳定性进行比较。数值结果表明两种方法对提高数值解的精度和调整问题求解区域的剖分起到明显的作用。     

Reconstructing Curves without Delaunay Computation

A new non-Delaunay-based approach is presented to reconstruct a curve, lying in 2- or 3-space, from a sampling of points. The underlying theory is based on bounding curvature to determine monotone pieces of the curve. Theoretical guarantees are established. The implemented algorithm, based heuristically on the theory, proceeds by iteratively partitioning the sample points using an octree data structure. The strengths of the approach are (a) simple implementation, (b) efficiency-experimental performance compares favorably with Delaunay-based algorithms, (c) robustness-curves with multiple components and sharp corners are reconstructed satisfactorily, and (d) potential extension to surface reconstruction.     

A Note on Point Location in Delaunay Triangulations of Random Points

This short note considers the problem of point location in a Delaunay triangulation of n random points, using no additional preprocessing or storage other than a standard data structure representing the triangulation. A simple and easy-to-implement (but, of course, worst-case suboptimal) heuristic is shown to take expected time O(n ^1/3 ) . Received November 27, 1997; revised February 15, 1998.     

喇叭增益的精确设计和精确计算

本文综述了作者和他人有关喇叭增益的精确设计与精确计算的理论结果,并且得出结论,举出实例。     

A Weighted Delaunay Triangulation Framework for Merging Triangulations in a Connectivity Oblivious Fashion

Simplicial meshes are useful as discrete approximations of continuous spaces in numerical simulations. In some applications, however, meshes need to be modified over time. Mesh update operations are often expensive and brittle, making the simulations unstable. In this paper we propose a framework for updating simplicial meshes that undergo geometric and topological changes. Instead of explicitly maintaining connectivity information, we keep a collection of weights associated with mesh vertices, using a Weighted Delaunay Triangulation (WDT). These weights implicitly define mesh connectivity and allow direct merging of triangulations. We propose two formulations for computing the weights, and two techniques for merging triangulations, and finally illustrate our results with examples in two and three dimensions.     

Coinduction for Exact Real Number Computation

This paper studies coinductive representations of real numbers by signed digit streams and fast Cauchy sequences. It is shown how the associated coinductive principle can be used to give straightforward and easily implementable proofs of the equivalence of the two representations as well as the correctness of various corecursive exact real number algorithms. The basic framework is the classical theory of coinductive sets as greatest fixed points of monotone operators and hence is different from (though related to) the type theoretic approach by Ciaffaglione and Gianantonio.     

Hypergeometric Functions in Exact Geometric Computation

Most problems in computational geometry are algebraic. A general approach to address nonrobustness in such problems is Exact Geometric Computation (EGC). There are now general libraries that support EGC for the general programmer (e.g., Core Library, LEDA Real). Many applications require non-algebraic functions as well. In this paper, we describe how to provide non-algebraic functions in the context of other EGC capabilities. We implemented a multiprecision hypergeometric series package which can be used to evaluate common elementary math functions to an arbitrary precision. This can be achieved relatively easily using the Core Library which supports a guaranteed precision level of accuracy. We address several issues of efficiency in such a hypergeometric package: automatic error analysis, argument reduction, preprocessing of hypergeometric parameters, and precomputed constants. Some preliminary experimental results are reported.     

Exact Computation of Polynomial Zeros Expressible by Square Roots

In this paper we give an efficient algorithm to find symbolically correct zeros of a polynomial f ∈ R[X] which can be represented by square roots. R can be any domain if a factorization algorithm over R[X] is given, including finite rings or fields, integers, rational numbers, and finite algebraic or transcendental extensions of those. Asymptotically, the algorithm needs O(T_f(d²)) operations in R, where T_f(d) are the operations for the factorization algorithm over R[X] for a polynomial of degree d. Thus, the algorithm has polynomial running time for instance for polynomials over finite fields or the rationals. We also present a quick test for deciding whether a given polynomial has zeros expressible by square roots and describe some additional methods for special cases.     

Isotropic Remeshing with Fast and Exact Computation of Restricted Voronoi Diagram

We propose a new isotropic remeshing method, based on Centroidal Voronoi Tessellation (CVT) . Constructing CVT requires to repeatedly compute Restricted Voronoi Diagram (RVD) , defined as the intersection between a 3D Voronoi diagram and an input mesh surface. Existing methods use some approximations of RVD. In this paper, we introduce an efficient algorithm that computes RVD exactly and robustly. As a consequence, we achieve better remeshing quality than approximation-based approaches, without sacrificing efficiency. Our method for RVD computation uses a simple procedure and a kd -tree to quickly identify and compute the intersection of each triangle face with its incident Voronoi cells. Its time complexity is O ( m log n ), where n is the number of seed points and m is the number of triangles of the input mesh. Fast convergence of CVT is achieved using a quasi-Newton method, which proved much faster than Lloyd's iteration. Examples are presented to demonstrate the better quality of remeshing results with our method than with the state-of-art approaches.     

Optimal Coding and Sampling of Triangulations

We present a bijection between the set of plane triangulations (aka maximal planar graphs) and a simple subset of the set of plane trees with two leaves adjacent to each node. The construction takes advantage of Schnyder tree decompositions of plane triangulations. This bijection yields an interpretation of the formula for the number of plane triangulations with n vertices. Moreover, the construction is simple enough to induce a linear random sampling algorithm, and an explicit information theory optimal encoding. Finally, we extend our bijection approach to triangulations of a polygon with k sides with m inner vertices, and develop in passing new results about Schnyder tree decompositions for these objects.     

用电营业管理信息系统中的电费计算模型研究

讨论了在用电营业管理信息系统建立过程中电费计算问题，给出了一种电费计算模型和算法实现。实践证明，此算法可解决以前在电费计算过程中广大用户的电费计算难以统一处理的问题。     

电力系统并行计算研究

介绍PC机群计算环境下的电力系统潮流计算模型,结合基于节点分割的网络分块方法和PC机群环境的特点,提出了一种基于网络数学分割的电力系统潮流分解协调算法.测试结果表明此算法具有较高的加速度和计算精度,适合在网络计算环境中实现.     

融合裕度和否决权的案例相似度量方法

现有相似度量方法未考虑关键属性的否决作用与虑属性值裕度对案例推理的影响。为此,提出一种新的案例相似度量方法。定义属性值裕度和关键属性否决权,采用布尔函数、熵值理论和Composite策略等数学理论和分析工具,设计否决权和裕度属性的相似度量公式,给出先局部后全局的合并策略。实例结果表明,该方法在保证相似度量效能的前提下,能提高案例相似度量的分辨率。     

Almost Regular Triangulations of Trimmend NURBS-Solids

An algorithm for constructing triangulations of three-dimensional trimmed NURBS-solids is described. Ideally, such triangulations consist entirely of congruent tetrahedra with nearly equal edges. The new feature of this method is that the position of the vertices is adjusted before any connecting edges are assigned. This leads to grids with very few irregular vertices, i.e. most interior vertices are shared by 24 tetrahedra, as for regular tessellations of R 3 with congruent tetrahedra.