Rectilinear steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors

We study the application of the geographic nearest neighbor approach to two problems. The first problem is the construction of an approximately minimum length rectilinear Steiner tree for a set ofn points in the plane. For this problem, we introduce a variation of a subgraph of sizeO(n) used by YaO [31] for constructing minimum spanning trees. Using this subgraph, we improve the running times of the heuristics discussed by Bern [6] fromO(n ² log n) toO(n log² n). The second problem is the construction of a rectilinear minimum spanning tree for a set ofn noncrossing line segments in the plane. We present an optimalO(n logn) algorithm for this problem. The rectilinear minimum spanning tree for a set of points can thus be computed optimally without using the Voronoi diagram. This algorithm can also be extended to obtain a rectilinear minimum spanning tree for a set of nonintersecting simple polygons.The results in this paper are a part of Y. C. Yee's Ph.D. thesis done at SUNY at Albany. He was supported in part by NSF Grants IRI-8703430 and CCR-8805782. S. S. Ravi was supported in part by NSF Grants DCI-86-03318 and CCR-89-05296.     

Insulating safety analysis of the hot-line sweeping robot

This paper presents a method of calculating the insulating safety distances for hot-line working robots at high voltage when dielectric is adulterated with conducts. Also, finite element method is adopted to calculate the electric field strength to find whether it is beyond the critical. The above methods have been applied to analyze the insulating safety of the robot for hot-line sweeping post insulators in a 220 KV substation. They have also been testified by experimentations.     

Dynamics of Balancing Space and Time in Memory: Tau and Kappa Effects Revisited.

In 3 experiments, the authors studied the organization of spatiotemporal information in memory. Stimuli consisted of configurations of dots, presented sequentially. The stimuli were either proportional, with interdot distances corresponding to interdot durations, or not proportional, with interdol distances not corresponding to interdot durations. After a learning phase, participants reproduced the spatial (Experiment 1), temporal (Experiment 2), or spatial and temporal (Experiment 3) characteristics of the target 60 times in succession. In the nonproportional conditions, effects of variable interdot durations or distances on the reproduction of, respectively, constant distances (tau effect) or durations (kappa effect) were observed, whereas no such effects were observed when variable distances or durations were to be produced. Tau and kappa effects influenced the accuracy but not the variability of responses. The results are discussed in light of the distinction between properties of the stabilized mental image and the process of stabilization. (PsycINFO Database Record (c) 2010 APA, all rights reserved)     

Peer-to-peer bichromatic reverse nearest neighbours in mobile ad-hoc networks

The increasing use of mobile communications has raised many issues of decision support and resource allocation. A crucial problem is how to solve queries of Reverse Nearest Neighbour (RNN). An RNN query returns all objects that consider the query object as their nearest neighbour. Existing methods mostly rely on a centralised base station. However, mobile P2P systems offer many benefits, including self-organisation, fault-tolerance and load-balancing. In this study, we propose and evaluate 3 distinct P2P algorithms focusing on bichromatic RNN queries, in which mobile query peers and static objects of interest are of two different categories, based on a time-out mechanism and a boundary polygon around the mobile query peers. The Brute-Force Search Algorithm provides a naive approach to exploit shared information among peers whereas two other Boundary Search Algorithms filter a number of peers involved in query processing. The algorithms are evaluated in the MiXiM simulation framework with both real and synthetic datasets. The results show the practical feasibility of the P2P approach for solving bichromatic RNN queries for mobile networks.     

基于DXF格式的优化数控代码自动生成方法

DXF是AutoCAD与其他软件进行数据交换的CAD通用图形文件格式。实现了一种DXF读取方式并自动生成数控加工代码。传统算法的读取结果无序,不适用于实际加工,针对这一问题根据提取结果及位置关系生成图元轮廓树,并利用最近邻插入算法对图元轮廓优化排序,得到全局优化的最短切割路径,并通过实例证实了算法的有效性,能满足实际自动编程数控系统的工作需要。     

LDE融合光谱回归分类的光照变化人脸识别

针对光照变化人脸识别问题中传统的光谱回归算法不能很好地进行特征提取而严重影响识别性能的问题,提出了局部判别嵌入优化光谱回归分类的人脸识别算法。计算出训练样本的特征向量;借助于数据的近邻和分类关系,利用局部判别嵌入算法构建分类问题所需的嵌入,同时学习每种分类的子流形所需的嵌入;利用光谱回归分类算法计算投影矩阵,并利用最近邻分类器完成人脸的识别。在两大人脸数据库扩展YaleB及CMU PIE上的实验验证了该算法的有效性,实验结果表明,相比其他光谱回归算法,该算法取得了更高的识别率、更好的工作特性,并且降低了计算复杂度。     

基于Voronoi图的连续反向最近邻查询

为解决动态环境中移动点的连续反向最近邻查询问题,将连续反向最近邻查询分为单色和双色2种情况进行研究。利用移动点Voronoi图,分别给出单色连续反向最近邻查询算法、双色连续反向最近邻查询算法以及相关定理,对算法正确性和可终止性进行证明,分析算法时间复杂性。按照移动点Voronoi图的拓扑结构是否改变分为2种情况,分析每种情况下候选所在区域的变化,在变化区域内进行Voronoi图的重构,得到对应的解决方法。在多数情况下,该算法只需生成局部移动点的Voronoi图即可找到结果,减小了连续反向最近邻查询的代价。     

一种基于自然最近邻的离群检测算法

任何涉及k近邻求解问题的算法被应用于处理不同特征的数据集时,参数k值的选择都会明显影响算法的性能和结果。因而,如何选择k近邻算法中敏感参数k值一直是一个研究难点。提出了一种新的近邻关系———自然最近邻,它不需要设置参数k,每个节点的邻居是由算法自适应计算而形成的。针对离群点检测的特殊性,通过确定自然最近邻居搜索算法的终止条件,提出一种基于自然最近邻的新的离群检测算法ODb3N。实验表明,该算法不仅避免了k近邻中参数的选择问题,而且能够更有效地发现离群簇。     

Dipole moments of copolymers in relation to the distribution of polar monomer unit sequences

A method for evaluating the dipole moments of copolymers in relation to the distribution of polar unit sequences is proposed. Experimental data on the synthesis and dipole moments of styrene-p-chlorostyrene and styrene-p-methoxystyrene copolymers were used to calculate the effective dipole moment of a polar unit in a copolymer. For this purpose, we assumed the following effective moment values for the corresponding polar unit sequences along the copolymer chains: when both of the nearest neighbours are polar, μ_PP, when one of the nearest neighbours is polar and the other is non-polar, μ_PS, and when both of the nearest neighbours are non-polar, μ_SS. The relative magnitudes of μ_SS, μ_PS and μ_PP calculated for both copolymers reflect the influence of dipole-dipole interactions on the effective dipole moment of a polar unit in a copolymer molecule.     

旅行商问题的较优可行解的搜索算法的设计

利用问题本身的特点和相关的已有结论,结合最近邻法和深度优先搜索算法设计了产生旅行商问题较优可行解的方法。首先,将与每个城市关联的城市由近到远排序,并将城市之间距离较远的边删除。然后选择一个城市作为出发地,按排序利用深度优先搜索算法在有限步内搜索可行解。若搜索到多个可行解,从中选择较优的作为以该城市为出发地的可行解;否则,重新选择出发地开始新的搜索。对经典的st70、a280问题依次将每个城市作为出发地进行实验,该方法产生的可行解的性能明显优于随机搜索算法。但仍不及最近邻法。