Efficiently navigating a random Delaunay triangulation

Planar graph navigation is an important problem with significant implications to both point location in geometric data structures and routing in networks. However, whilst a number of algorithms and existence proofs have been proposed, very little analysis is available for the properties of the paths generated and the computational resources required to generate them under a random distribution hypothesis for the input. In this paper we analyse a new deterministic planar navigation algorithm with constant spanning ratio (w.r.t the Euclidean distance) which follows vertex adjacencies in the Delaunay triangulation. We call this strategy cone walk. We prove that given n uniform points in a smooth convex domain of unit area, and for any start point z and query point q; cone walk applied to z and q will access at most sites with complexity with probability tending to 1 as n goes to infinity. We additionally show that in this model, cone walk is ‐memoryless with high probability for any pair of start and query point in the domain, for any positive ξ. We take special care throughout to ensure our bounds are valid even when the query points are arbitrarily close to the border. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 95–136, 2016     

空间编码与灰度投影相结合实现高效3-D形貌测量的研究

介绍了一种结合空间编码与灰度投影来实现高效三维形貌测量的方法。用空间编码完成对被测空间的粗略编码,用灰度投影完成精确编码,将它们结合起来得到被测物体表面丰富的编码信息,作为一种基于三角法的三维形貌测量方法,能够在物体表面非常不连续和外部光照造成的背景光强分布不确定的情况下工作良好。同时,与传统的空间编码方法相比,它大大提高了空间编码的效率。实验表明,该方法用５ 幅图像取得了与灰度码１０幅图像相当的测量结果。     

基于空间二进制编码的3 D形貌测量方法

介绍了一种基于空间二进制编码的非接触３ Ｄ 形貌测量方法。它用一台ＬＣＤ 投影仪对被测物体表面进行空间编码,再用一台ＣＣＤ 摄像机获取物体编码信息,最后用三角法原理从摄像机图像中获取三维形貌数据。提出了基于三角法的空间二进制码的重要特性,描述了高效编码的构造方法。用这个构造方法构造出一个完全数字化的７ 位字长的二进制编码。基于这种编码的３ Ｄ 形貌测量方法在被测物体表面非常不连续和非构造的环境下取得了良好的测量结果。     

Computing a Minimum Weight Triangulation of a Sparse Point Set*

Investigating the minimum weight triangulation of a point set with constraint is an important approach for seeking the ultimate solution of the minimum weight triangulation problem. In this paper, we consider the minimum weight triangulation of a sparse point set, and present an O(n ⁴) algorithm to compute a triangulation of such a set. The property of sparse point set can be converted into a new sufficient condition for finding subgraphs of the minimum weight triangulation. A special point set is exhibited to show that our new subgraph of minimum weight triangulation cannot be found by any currently known methods.     

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).