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.     

A Novel Segmentation and Feedback Model for Resolving Contention in Optical Burst Switching

A novel segmentation and feedback model (SFM) applied to resolve contention is proposed. Simulation and performance analyses show that the SFM effectively avoids contentions in optical burst switching (OBS). The long delay time of deflection routing and the immature technology of wavelength converters and optical buffers are not deployed in the SFM. The SFM does not only realize fast switching but also allows preemption by higher priority bursts.     

Applications of Telos

EuLisp has an integrated object system with reflective capabilities. We discuss some example applications which use these facilities to experiment with some advanced and powerful concepts, namely, finalization, virtual shared memory and persistence. A secondary goal is to attempt to illustrate the additional possibilities of metaobject programming over non-metalevel techniques.     

Algorithm for finding all k nearest neighbors

A very simple algorithm for computing all k nearest neighbors in 2-D is presented. The method does not rely on complicated forms of tessellation, it only requires simple data binning for fast range searching. Its applications range from scattered data interpolation to reverse engineering.     

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.     

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

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

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

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

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

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

基于RTX的工程飞行模拟器数据采集与存储系统设计

在一些仿真应用中,由于Windows操作系统较差的实时性,从而给许多半物理仿真试验带来了一些不确定的因素.在充分论证的基础上,引入了Ardence公司的基于Windows的硬实时解决方案RTX（Real-Time eXtension）,并结合某型号飞行器仿真课题总结出了Windows环境下RTX实时应用系统的设计方法与开发流程以及RTX下硬件板卡驱动程序的编写,最后将这种设计方法成功应用在某型号飞行器飞行仿真系统中.实验证明该仿真系统是可靠的、稳定的,整个实验过程中飞行器的飞行数据没有丢失,仿真周期确定,结果正确,RTX仿真程序能够满足系统对实时性和确定性的要求.