Hamilton cycles in plane triangulations

We extend Whitney's Theorem that every plane triangulation without separating triangles is hamiltonian by allowing some separating triangles. More precisely, we define a decomposition of a plane triangulation G into 4‐connected ‘pieces,’ and show that if each piece shares a triangle with at most three other pieces then G is hamiltonian. We provide an example to show that our hypothesis that each piece shares a triangle with at most three other pieces' cannot be weakened to ‘four other pieces.’ As part of our proof, we also obtain new results on Tutte cycles through specified vertices in planar graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 138–150, 2002     

基于线结构光的三维测量系统关键技术研究

提出了一种基于线激光、工业相机 、步进电机和 计算机的结构光的单目视觉三维扫描测量系统,阐述了其工作原理,建立几何数学模型,搭 建了系统试验平台,并基于灰度平方加权重心法提取光条中心。实验结果表明, 系统测量误差小于±0.03mm,光条中心提取精度达到亚像素级,满 足工业测量应用需求。     

基于改进灰度重心法的光带中心提取算法

在线结构光三维测量中,由于线结构光光源质量、物体表面反射率非均匀性以及表面粗糙性等因素的影响,激光光带经常会出现宽度不均匀,光带亮度不集中、离散性较大的现象。本文提出一种改进灰度重心法提取激光光带中心线,该算法基于自适应二值化处理得到光带各列法向宽度值以及光带的准确边界。然后,利用光带边界与灰度数据进行灰度重心计算确定出光带的中心位置。结果证实,改进算法中灰度重心的计算范围与光带宽度相一致,因而具有较高的提取精度和良好的适应性。     

On a proper acute triangulation of a polyhedral surface

Let Σ be a polyhedral surface in R³ with n edges. Let L be the length of the longest edge in Σ, δ be the minimum value of the geodesic distance from a vertex to an edge that is not incident to the vertex, and θ be the measure of the smallest face angle in Σ. We prove that Σ can be triangulated into at most CLn/(δθ) planar and rectilinear acute triangles, where C is an absolute constant.     

On the stretch factor of Delaunay triangulations of points in convex position

Let S be a finite set of points in the Euclidean plane. Let G be a geometric graph in the plane whose point set is S. The stretch factor of G is the maximum ratio, among all points p and q in S, of the length of the shortest path from p to q in G over the Euclidean distance |pq|. Keil and Gutwin in 1989 [11] proved that the stretch factor of the Delaunay triangulation of a set of points S in the plane is at most 2π/(3cos(π/6))≈2.42. Improving on this upper bound remains an intriguing open problem in computational geometry.In this paper we consider the special case when the points in S are in convex position. We prove that in this case the stretch factor of the Delaunay triangulation of S is at most ρ=2.33.     

助航灯具光强测试系统研究

针对助航灯具的发光特性,提出了一种测试助航灯具出射光强分布的方法。使用线阵CCD作为光电传感器,采集、获取各个方向灯具的光强信号,利用A/D芯片和USB接口芯片实现数据的转化和实时传输。通过改进的Delaunay三角剖分线算法和B样条曲线平滑处理算法的结合,提出了一种快速生成等光强曲线的算法,给出了Matlab软件获得等光强曲线的方法。通过对PAPI灯出射光强的测试及其等光强曲线的拟合,验证了该测试装置可以较好地实现光强测试,所提算法绘制的曲线平滑、速度快。     

On plane geometric spanners: A survey and open problems

Given a weighted graph $G=(V,E)$ and a real number $t?1$, a t-spanner of G is a spanning subgraph $G^{\prime }$ with the property that for every edge xy in G, there exists a path between x and y in $G^{\prime }$ whose weight is no more than t times the weight of the edge xy. We review results and present open problems on different variants of the problem of constructing plane geometric t-spanners.     

Estimating a Nonstationary Spatial Structure Using Simulated Annealing

During the past decade, a useful model for nonstationary random fields has been developed. This consists of reducing the random field of interest to isotropy via a bijective bi-continuous deformation of the index space. Then the problem consists of estimating this space deformation together with the isotropic correlation in the deformed index space. We propose to estimate both this space deformation and this isotropic correlation using a constrained continuous version of the simulated annealing for a Metropolis-Hastings dynamic. This method provides a nonparametric estimation of the deformation which has the required property to be bijective; so far, the previous nonparametric methods do not guarantee this property. We illustrate our work with two examples, one concerning a precipitation dataset. We also give one idea of how spatial prediction should proceed in the new coordinate space.     

结构现场可调的点激光精密测量系统

为了实现激光传感器测头可以根据现场条件来实时改变入射角度,建立了结构可调的点激光测量系统。建立了相机的针孔模型,利用张正友标定算法得到该相机模型的内部参数,定义点激光测量系统中的光心角,推导出利用像点坐标和相机内部参数实时求取光心角公式。建立了点激光测量系统的数学模型,引入点激光测量系统的结构参数:基线距和基准角,利用零平面和两个基准面标定系统结构参数。利用标定得到的系统结构参数进行实时的逆向工程在线测量。实验结果表明:测量系统量程为75mm时,该标定算法最大标定误差≤0.02mm,点激光测量系统的测量误差≤0.06mm,达到精密测量的要求。