Design and analysis of planar shape deformation

Shape deformation refers to the continuous change of one geometric object to another. We develop a software tool for planning, analyzing and visualizing deformations between two shapes in . The deformation is generated automatically without any user intervention or specification of feature correspondences. A unique property of the tool is the explicit availability of a two-dimensional shape space, which can be used for designing the deformation either automatically by following constraints and objectives or manually by drawing deformation paths.     

An iterative method for the creation of structured hexahedral meshes over complex orography

In this paper we propose a technique for measuring the quality of hexahedral Cartesian meshes used to model meso-scale atmospheric circulation in 3D. It is used to verify the progress of a novel method for satisfying the Delaunay criterion for structured hexahedral meshes over complex orography with high gradients and wide gradient variability. Based on a simile with potential energy, the iterative method of mesh smoothing is shown to improve mesh quality with logarithmic convergence. The method is evaluated in a practical application in a specific geographic location.     

On well-covered triangulations: Part II

A graph G is said to be well-covered if every maximal independent set of vertices has the same cardinality. A planar (simple) graph in which each face is a triangle is called a triangulation. It was proved in an earlier paper [A. Finbow, B. Hartnell, R. Nowakowski, M. Plummer, On well-covered triangulations: Part I, Discrete Appl. Math., 132, 2004, 97-108] that there are no 5-connected planar well-covered triangulations. It is the aim of the present paper to completely determine the 4-connected well-covered triangulations containing two adjacent vertices of degree 4. In a subsequent paper [A. Finbow, B. Hartnell, R. Nowakowski, M. Plummer, On well-covered triangulations: Part III (submitted for publication)], we show that every 4-connected well-covered triangulation contains two adjacent vertices of degree 4 and hence complete the task of characterizing all 4-connected well-covered planar triangulations. There turn out to be only four such graphs. This stands in stark contrast to the fact that there are infinitely many 3-connected well-covered planar triangulations.     

On the sizes of Delaunay meshes

Let be a polyhedral domain occupying a convex volume. We prove that the size of a graded mesh of with bounded vertex degree is within a factor of the size of any Delaunay mesh of with bounded radius-edge ratio. The term depends on the geometry of and it is likely a small constant when the boundaries of are fine triangular meshes. There are several consequences. First, among all Delaunay meshes with bounded radius-edge ratio, those returned by Delaunay refinement algorithms have asymptotically optimal sizes. This is another advantage of meshing with Delaunay refinement algorithms. Second, if no input angle is acute, the minimum Delaunay mesh with bounded radius-edge ratio is not much smaller than any minimum mesh with aspect ratio bounded by a particular constant.     

Free and nonfree Voronoi polyhedra

The Voronoi polyhedron of some point v of a translation lattice is the closure of the set of points in space that are closer to v than to any other lattice points. Voronoi polyhedra are a special case of parallelohedra, i.e., polyhedra whose parallel translates can fill the entire space without gaps and common interior points. The Minkowski sum of a parallelohedron with a segment is not always a parallelohedron. A parallelohedron P is said to be free along a vector e if the sum of P with a segment of the line spanned by e is a parallelohedron. We prove a theorem stating that if the Voronoi polyhedron P _v (f) of a quadratic form f is free along some vector, then the Voronoi polyhedron P _v (g) of each form g lying in the closure of the L-domain of f is also free along some vector. For the dual root lattice E ₆*, and the infinite series of lattices D _2m ⁺ , m ≥ 4, we prove that their Voronoi polyhedra are nonfree in all directions.     

Dominating sets in triangulations on surfaces

Let G be a graph and let S?V(G). We say that S is dominating in G if each vertex of G is in S or adjacent to a vertex in S. We show that every triangulation on the torus and the Klein bottle with n vertices has a dominating set of cardinality at most $\frac{n}{3}Let G be a graph and let S?V(G). We say that S is dominating in G if each vertex of G is in S or adjacent to a vertex in S. We show that every triangulation on the torus and the Klein bottle with n vertices has a dominating set of cardinality at most $\frac{n}{3}$. Moreover, we show that the same conclusion holds for a triangulation on any non‐spherical surface with sufficiently large representativity. These results generalize that for plane triangulations proved by Matheson and Tarjan (European J Combin 17 (1996), 565–568), and solve a conjecture by Plummer (Private Communication). © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 17–30, 2010     

��˹ͼģ�͵Ļ����������Ľ���IPSP�㷨

The IPSP algorithm is an efficient algorithm for computing maximum likelihood estimation of Gaussian graphical models. It first divides clique marginals of graphical models into several groups, and then it adjusts clique marginals in each group locally. This paper uses the IIPS algorithm on junction tree to replace local adjustment on each group in the IPSP algorithm and propose a resulting algorithm called IPSP-JT to reduce the complexity of the IPSP algorithm. Moreover, we give a graph with minimum edges used by IIPS to adjust locally, and we prove its existence and uniqueness and construct a local junction tree. Numerical experiments show that the IPSP-JT algorithm runs faster than the IPSP algorithm for large Gaussian graphical models.     

R-Local Delaunay Inhibition Model

Unlike in the classical framework of Gibbs point processes (usually acting on the complete graph), in the context of nearest-neighbour Gibbs point processes the nonnegativeness of the interaction functions do not ensure the local stability property. This paper introduces domain-wise (but not pointwise) inhibition stationary Gibbs models based on some tailor-made Delaunay subgraphs. All of them are subgraphs of the R-local Delaunay graph, defined as the Delaunay subgraph specifically not containing the edges of Delaunay triangles with circumscribed circles of radii greater than some large positive real value R. The usual relative compactness criterion for point processes needed for the existence result is directly derived from the Ruelle-bound of the correlation functions. Furthermore, assuming only the nonnegativeness of the energy function, we have managed to prove the existence of the existence of R-local Delaunay stationary Gibbs states based on nonnegative interaction functions thanks to the use of the compactness of sublevel sets of the relative entropy. In memory of Etienne Bertin.     

Recursive constructions for triangulations

Three recursive constructions are presented; two deal with embeddings of complete graphs and one with embeddings of complete tripartite graphs. All three facilitate the construction of 2) non‐isomorphic face 2‐colourable triangulations of K_n and K_n,n,n in orientable and non‐orientable surfaces for values of n lying in certain residue classes and for appropriate constants a. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 87–107, 2002     

快速三维散乱数据点重建算法

提出了一种快速三维散乱数据点重建算法.我们对包围盒算法进行了改进,减少了建立散乱点近邻关系所需的计算量;同时针对位置相对平坦的数据点,结合最小二乘法给出了一种计算法矢的混合方法.实例表明,该算法是有效的.