Anisotropic unstructured mesh adaption for flow simulations

Three new ideas for anisotropic adaption of unstructured triangular grids are presented, with particular emphasis on fluid flow computations. © 1997 John Wiley & Sons, Ltd.     

激光三角法测量中被测物表面特性对测量精度影响的分析

激光三角法测量是现代测量技术中重要的测量方法,但其测量精度受自身系统、环境以及被测物表面特征等因素的影响。针对被测表面的特性是激光三角法产生测量中产生测量误差的主要因素,根据特定颜色所造成误差的重复特性提出了数据标定的改进方法;针对表面粗糙度,通过在光路适当位置安装偏振片有效消除了镜面反射,采用双光路设计有效改善了被测物倾斜带来的误差。最后通过实验验证了改进方法的有效性。     

Manifold Reconstruction in Arbitrary Dimensions Using Witness Complexes

It is a well-established fact that the witness complex is closely related to the restricted Delaunay triangulation in low dimensions. Specifically, it has been proved that the witness complex coincides with the restricted Delaunay triangulation on curves, and is still a subset of it on surfaces, under mild sampling conditions. In this paper, we prove that these results do not extend to higher-dimensional manifolds, even under strong sampling conditions such as uniform point density. On the positive side, we show how the sets of witnesses and landmarks can be enriched, so that the nice relations that exist between restricted Delaunay triangulation and witness complex hold on higher-dimensional manifolds as well. We derive from our structural results an algorithm that reconstructs manifolds of any arbitrary dimension or co-dimension at different scales. The algorithm combines a farthest-point refinement scheme with a vertex pumping strategy. It is very simple conceptually, and it does not require the input point sample to be sparse. Its running time is bounded by c(d)n ², where n is the size of the input point cloud, and c(d) is a constant depending solely (yet exponentially) on the dimension d of the ambient space. Although this running time makes our reconstruction algorithm rather theoretical, recent work has shown that a variant of our approach can be made tractable in arbitrary dimensions, by building upon the results of this paper. This work was done while S.Y. Oudot was a post-doctoral fellow at Stanford University. His email there is no longer valid.     

Matching Points with Squares

Given a class of geometric objects and a point set P, a -matching of P is a set of elements of such that each C _i contains exactly two elements of P and each element of P lies in at most one C _i . If all of the elements of P belong to some C _i , M is called a perfect matching. If, in addition, all of the elements of M are pairwise disjoint, we say that this matching M is strong. In this paper we study the existence and characteristics of -matchings for point sets in the plane when is the set of isothetic squares in the plane. A consequence of our results is a proof that the Delaunay triangulations for the L _∞ metric and the L ₁ metric always admit a Hamiltonian path.     

K6‐minors in triangulations and complete quadrangulations

In this paper, we shall prove that a projective‐planar (resp., toroidal) triangulation G has K₆ as a minor if and only if G has no quadrangulation isomorphic to K₄ (resp., K₅ ) as a subgraph. As an application of the theorems, we can prove that Hadwiger's conjecture is true for projective‐planar and toroidal triangulations. © 2009 Wiley Periodicals, Inc. J Graph Theory 60: 302‐312, 2009     

An algorithm for three-dimensional Voronoi S-network

The paper presents an algorithm for calculating the three-dimensional Voronoi-Delaunay tessellation for an ensemble of spheres of different radii (additively-weighted Voronoi diagram). Data structure and output of the algorithm is oriented toward the exploration of the voids between the spheres. The main geometric construct that we develop is the Voronoi S-network (the network of vertices and edges of the Voronoi regions determined in relation to the surfaces of the spheres). General scheme of the algorithm and the key points of its realization are discussed. The principle of the algorithm is that for each determined site of the network we find its neighbor sites. Thus, starting from a known site of the network, we sequentially find the whole network. The starting site of the network is easily determined based on certain considerations. Geometric properties of ensembles of spheres of different radii are discussed, the conditions of applicability and limitations of the algorithm are indicated. The algorithm is capable of working with a wide variety of physical models, which may be represented as sets of spheres, including computer models of complex molecular systems. Emphasis was placed on the issue of increasing the efficiency of algorithm to work with large models (tens of thousands of atoms). It was demonstrated that the experimental CPU time increases linearly with the number of atoms in the system, O(n).     

基于背景网格变形的动态网格移动方法

基于Delaunay背景网格插值技术的动态网格生成方法无需迭代计算,效率较高。但对复杂构形大幅运动的动边界问题,尤其当边界大幅转动时,背景网格极易交叉重叠。重新生成背景网格和重新定位网格节点信息不仅费时而且会导致网格质量的严重下降。本文提出改进的基于背景网格的动态网格变形方法,通过在初始Delaunay背景网格中添加辅助点,生成一层新的背景网格和新的映射关系;采用ball-vertex弹簧法驱动新背景网格的变形,进而牵动目标网格的变形。算例表明,本文提出的动态网格变形方法对所关心区域的网格具有良好保形性,边界可转动更大角度而不会出现网格交叉重叠问题,总体上提高了动态网格更新的效率和质量。     

高质量点集的快速局部网格生成算法

高效及高质量的局部网格生成算法是基于节点有限元并行方法设计的关键。泡泡布点算法能够在复杂区域上不经过人工干预生成高质量的节点集,本文提出了基于该方法所生成的节点集的快速局部网格生成算法。该算法充分利用泡泡布点方法提供的节点集及节点邻接链表信息,避免了桶数据结构的建立以及节点的局部搜索过程,只需应用Delaunay三角剖分的外接圆准则从中心节点的邻接链表中去除极少数的非卫星点,可快速地生成局部网格,比现有的局部网格生成算法更为快捷。算例结果表明,该算法高效可靠,生成网格与Delaunay三角剖分网格一致。     

逐点插入法在三维地质建模中的运用

随着科学计算可视化技术和地质信息技术的发展,三维地质建模逐渐成为石油勘探、岩土工程、GIS和科学计算可视化等领域研究与应用的热点。本文主要介绍了在三维地质建模中常用的三角剖分算法中的逐点插入法,在实际运用中进行了改进,对三维空间中的原始数据点进行三角网化并构造地质体。     

Beta‐decomposition for the volume and area of the union of three‐dimensional balls and their offsets

Given a set of spherical balls, called atoms, in three‐dimensional space, its mass properties such as the volume and the boundary area of the union of the atoms are important for many disciplines, particularly for computational chemistry/biology and structural molecular biology. Despite many previous studies, this seemingly easy problem of computing mass properties has not been well‐solved. If the mass properties of the union of the offset of the atoms are to be computed as well, the problem gets even harder. In this article, we propose algorithms that compute the mass properties of both the union of atoms and their offsets both correctly and efficiently. The proposed algorithms employ an approach, called the Beta‐decomposition, based on the recent theory of the beta‐complex. Given the beta‐complex of an atom set, these algorithms decompose the target mass property into a set of primitives using the simplexes of the beta‐complex. Then, the molecular mass property is computed by appropriately summing up the mass property corresponding to each simplex. The time complexity of the proposed algorithm is O(m) in the worst case where m is the number of simplexes in the beta‐complex that can be efficiently computed from the Voronoi diagram of the atoms. It is known in ?³ that m = O(n) on average for biomolecules and m = O(n²) in the worst case for general spheres where n is the number of atoms. The theory is first introduced in ?² and extended to ?³. The proposed algorithms were implemented into the software BetaMass and thoroughly tested using molecular structures available in the Protein Data Bank. BetaMass is freely available at the Voronoi Diagram Research Center web site. © 2012 Wiley Periodicals, Inc.