Small Strictly Convex Quadrilateral Meshes of Point Sets

In this paper we give upper and lower bounds on the number of Steiner points required to construct a strictly convex quadrilateral mesh for a planar point set. In particular, we show that 3\lfloorn/2\rfloor internal Steiner points are always sufficient for a convex quadrilateral mesh of n points in the plane. Furthermore, for any given n\geq 4, there are point sets for which \lceil(n–3)/2\rceil–1 Steiner points are necessary for a convex quadrilateral mesh.     

On Optimal Bilinear Quadrilateral Meshes

The novelty of this work is in presenting interesting error properties of two types of asymptotically ‘optimal’ quadrilateral meshes for bilinear approximation. The first type of mesh has an error equidistributing property, where the maximum interpolation error is asymptotically the same over all elements. The second type has faster than expected ‘super-convergence’ property for certain saddle-shaped data functions. The ‘super-convergent’ mesh may be an order of magnitude more accurate than the error equidistributing mesh. Both types of mesh are generated by a coordinate transformation of a regular mesh of squares. The coordinate transformation is derived by interpreting the Hessian matrix of a data function as a metric tensor. The insights in this work may have application in mesh design near known corner or point singularities.     

Transformation of Hexaedral Finite Element Meshes into Tetrahedral Meshes According to Quality Criteria

The paper is concerned with algorithms for transforming hexahedral finite element meshes into tetrahedral meshes without introducing new nodes. Known algorithms use only the topological structure of the hexahedral mesh but no geometry information. The paper provides another algorithm which is then extented such that quality criteria for the splitting of faces are respected.     

平面点集凸包快速构建算法的研究

文章提出了一种提高构建凸包速度的新方法。该算法生成一个网格来管理离散点,在淘汰明显不位于凸包上的点时,将对离散点的取舍转换为对格的取舍,计算工作量只与离散点的范围及网格的密度有关,与离散点的数目无关;同时对点集也进行了初略的排序。在求取剩余点集的凸包时,采用了一种先分段求取凸包边界,最后将这些边界合并成凸包的方法,该方法充分利用了剩余点集所具有的有序性。     

一种基于凸集投影(POCS)的数字图像超分辨率重建算法

该文研究了一种基于凸集投影(POCS)算法的超分辨率图像重建方法,分析了POCS方法恢复图像的理论算法,通过仿真对比了其与双线性插值方法恢复超分辨率图像的差异,仿真结果表明,该方法明显地提高了超分辨率图像的恢复质量。     

Automatic mesh generation and modification techniques for mixed quadrilateral and hexahedral element meshes of non-manifold models

A typical geometric model usually consists of both solid sections and thin-walled sections. Through using a suitable dimensional reduction algorithm, the model can be reduced to a non-manifold model consisting of solid portions and two-dimensional portions which represent the mid-surfaces of the thin-walled sections. It is desirable to mesh the solid entities using three-dimensional elements and the surface entities using two-dimensional elements. This paper proposes a robust scheme to automatically generate such a mesh of mixed two-dimensional and three-dimensional elements. It also ensures that the mesh is conforming at the interface of the non-manifold geometries. Different classes of problems are identified and their corresponding solutions are presented.     

Scale Space Meshing of Raw Data Point Sets

This paper develops a scale space strategy for orienting and meshing exactly and completely a raw point set. The scale space is based on the intrinsic heat equation, also called mean curvature motion (MCM). A simple iterative scheme implementing MCM directly on the raw point set is described, and a mathematical proof of its consistency with MCM is given. Points evolved by this MCM implementation can be trivially backtracked to their initial raw position. Therefore, both the orientation and mesh of the data point set obtained at a smooth scale can be transported back on the original. The gain in visual accuracy is demonstrated on archaeological objects by comparison with several state of the art meshing methods.     

Communication-Aware Processor Allocation for Supercomputers: Finding Point Sets of Small Average Distance

We give processor-allocation algorithms for grid architectures, where the objective is to select processors from a set of available processors to minimize the average number of communication hops. The associated clustering problem is as follows: Given n points in ℜ ^d , find a size-k subset with minimum average pairwise L ₁ distance. We present a natural approximation algorithm and show that it is a -approximation for two-dimensional grids; in d dimensions, the approximation guarantee is , which is tight. We also give a polynomial-time approximation scheme (PTAS) for constant dimension d, and we report on experimental results.