An Optimized Divide-and-Conquer Algorithm for the Closest-Pair Problem in the Planar Case

We present an engineered version of the divide-and-conquer algorithm for finding the closest pair of points,within a given set of points in the XY-plane.For this version of the algorithm we show that only two pairwise comparisons are required in the combine step,for each point that lies in the 2δ-wide vertical slab.The correctness of the algorithm is shown for all Minkowski distances with p 1.We also show empirically that,although the time complexity of the algorithm is still O(n lg n),the reduction in the total number of comparisons leads to a significant reduction in the total execution time,for inputs with size sufficiently large.     

On Some Proximity Problems of Colored Sets

The maximum diameter color-spanning set problem（MaxDCS） is defined as follows： given n points with m colors, select m points with m distinct colors such that the diameter of the set of chosen points is maximized. In this paper, we design an optimal O（n log n） time algorithm using rotating calipers for MaxDCS in the plane. Our algorithm can also be used to solve the maximum diameter problem of imprecise points modeled as polygons. We also give an optimal algorithm for the all farthest foreign neighbor problem（AFFN） in the plane, and propose algorithms to answer the farthest foreign neighbor query（FFNQ） of colored sets in two- and three-dimensional space. Furthermore, we study the problem of computing the closest pair of color-spanning set（CPCS） in d-dimensional space, and remove the log m factor in the best known time bound if d is a constant.     

Efficient Parallel Algorithms for Some Graph Theory Problems

In this paper,a sequential algorithm computing the aww vertex pair distance matrix D and the path matrix Pis given.On a PRAM EREW model with p,1≤p≤n^2,processors,a parallel version of the sequential algorithm is shown.This method can also be used to get a parallel algorithm to compute transitive closure array A^* of an undirected graph.The time complexity of the parallel algorithm is O(n^3/p).If D,P and A^* are known,it is shown that the problems to find all connected components,to compute the diameter of an undirected graph,to determine the center of a directed graph and to search for a directed cycle with the minimum(maximum)length in a directed graph can all be solved in O(n^2/p logp)time.     

A New Line Symmetry Distance and Its Application to Data Clustering

In this paper,at first a new line-symmetry-based distance is proposed.The properties of the proposed distance are then elaborately described.Kd-tree-based nearest neighbor search is used to reduce the complexity of computing the proposed line-symmetry-based distance.Thereafter an evolutionary clustering technique is developed that uses the new linesymmetry -based distance measure for assigning points to different clusters.Adaptive mutation and crossover probabilities are used to accelerate the proposed c...     

Composite Distance Transformation for Indexing and k-Nearest-Neighbor Searching in High-Dimensional Spaces

Due to the famous dimensionality curse problem, search in a high-dimensional space is considered as a ＂hard＂ problem. In this paper, a novel composite distance transformation method, which is called CDT, is proposed to support a fast κ-nearest-neighbor （κ-NN） search in high-dimensional spaces. In CDT, all （n） data points are first grouped into some clusters by a κ-Means clustering algorithm. Then a composite distance key of each data point is computed. Finally, these index keys of such n data points are inserted by a partition-based B^＋-tree. Thus, given a query point, its κ-NN search in high-dimensional spaces is transformed into the search in the single dimensional space with the aid of CDT index. Extensive performance studies are conducted to evaluate the effectiveness and efficiency of the proposed scheme. Our results show that this method outperforms the state-of-the-art high-dimensional search techniques, such as the X-Tree, VA-file, iDistance and NB-Tree.     

Sparse representation based on projection method in online least squares support vector machines

A sparse approximation algorithm based on projection is presented in this paper in order to overcome the limitation of the non-sparsity of least squares support vector machines （LS-SVM）. The new inputs are projected into the subspace spanned by previous basis vectors （BV） and those inputs whose squared distance from the subspace is higher than a threshold are added in the BV set, while others are rejected. This consequently results in the sparse approximation. In addition, a recursive approach to deleting an exiting vector in the BV set is proposed. Then the online LS-SVM, sparse approximation and BV removal are combined to produce the sparse online LS-SVM algorithm that can control the size of memory irrespective of the processed data size. The suggested algorithm is applied in the online modeling of a pH neutralizing process and the isomerization plant of a refinery, respectively. The detailed comparison of computing time and precision is also given between the suggested algorithm and the nonsparse one. The results show that the proposed algorithm greatly improves the sparsity just with little cost of precision.     

Engineering the Divide-and-Conquer Closest Pair Algorithm

We improve the famous divide-and-conquer algorithm by Bentley and Shamos for the planar closest-pair problem. For n points on the plane, our algorithm keeps the optimal O（n log n） time complexity and, using a circle-packing property, computes at most 7n/2 Euclidean distances, which improves Ge et al.＇s bound of （3n log n）/2 Euclidean distances. We present experimental results of our comparative studies on four different versions of the divide-and-conquer closest pair algorithm and propose two effective heuristics.     

Discrete Interpolation Surface

In this paper,a method to construct a surface with point interpolation and normal interpolation is presented.An algorithm to construct the discrete interpolation is also presented,which has the time complexity O(Nlog N),where N in the number of scattered points.     

Composite Distance Transformation for Indexing and k-Nearest-Neighbor Searching in High-Dimensional Spaces

Due to the famous dimensionality curse problem, search in a high-dimensional space is considered as a "hard" problem. In this paper, a novel composite distance transformation method, which is called CDT, is proposed to support a fast k-nearest-neighbor (k-NN) search in high-dimensional spaces. In CDT, all (n) data points are first grouped into some clusters by a k-Means clustering algorithm. Then a composite distance key of each data point is computed. Finally, these index keys of such n data points are inserted by a partition-based B -tree. Thus, given a query point, its k-NN search in high-dimensional spaces is transformed into the search in the single dimensional space with the aid of CDT index. Extensive performance studies are conducted to evaluate the effectiveness and efficiency of the proposed scheme. Our results show-that this method outperforms the state-of-the-art high-dimensional search techniques, such as the X-Tree, VA-file, iDistance and NB-Tree.     

A low-complexity ECG processing algorithm based on the Haar wavelet transform for portable health-care devices

This paper presents a simple Electrocardiogram （ECG） processing algorithm for portable healthcare devices. This algorithm consists of the Haar wavelet transform （HWT）, the modulus maxima pair detection （MMPD） and the peak position modification （PPM）. To lessen the computational complexity, a novel no multiplier structure is introduced to implement HWT. In the MMPD, the HWT coefficient at scale 24 is processed to find candidate peak positions of ECG. The PPM is designed to correct the time shift in digital process and accurately determine the location of peaks. Some new methods are proposed to improve anti-jamming per- formance in MMPD and PPM. Evaluated by the MIT-BIH arrhythmia database, the sensitivity （Se） of QRS detection is 99.53% and the positive prediction （Pr） of QRS detection is 99.70%. The QT database is chosen to fully validate this algorithm in complete delineation of ECG waveform. The mean # and standard deviation cr between test results and annotations are calculated. Most of a satisfies the CSE limits which indicates that the results are stable and reliable. A detailed and rigorous computational complexity analysis is presented in this paper. The number of arithmetic operations in N input samples is chosen as the criterion of complexity. Without any multiplication operations, the number of addition operations is only about 16.33N. This algorithm achieves high detection accuracy and the lower computational complexity.     

基因组Translocation排序问题的改进多项式算法

该文给出基因组Transhocation排序问题的一个改进多项式算法，原算法所有存储空间O（n)，时间复杂度为O(n^3)，文中改进算法仍采用O(n)存储空间，时间复杂度为O(n^2logn),具体地，将计算Translocation距离的时间复杂度由O(n^3)改进为O(n^2),将计算Translocation序列的时间复杂度由O(n^3)改进为O(n^2logn).     

求平面点集最近点对的一个改进算法

文中对Ｐｒｅｐａｒａｔａ和Ｓｈａｍｏｓ在１９８５年提出的求平面点集最近点对的一个分治算法进行了改进，使原来 归并时最多需计处３ｎ对点对的距离，改进的为最多只需计算２ｎ     

求一个包含点集所有点的最小圆的算法

提出一种算法,以解决求一个最小圆包含给定点集所有点的问题.证明了这种算法的时间复杂性为O(|lg(d/R)|*n),其中R是所求的最小圆的半径,d为点集中不在圆周上但距圆周最近的点到圆周的距离.     

A fast parallel algorithm for routing unicast assignments in Benesnetworks

This paper presents a new parallel algorithm for routing unicast (one-to-one) assignments in Benes networks. Parallel routing algorithms for such networks were reported earlier, but these algorithms were designed primarily to route permutation assignments. The routing algorithm presented in this paper removes this restriction without an increase in the order of routing cost or routing time. We realize this new routing algorithm on two different topologies. The algorithm routes a unicast assignment involving O(k) pairs of inputs and outputs in O(lg ² k+lg n) time on a completely connected network of n processors and in O(lg⁴ k+lg² k lg n) time on an extended shuffle-exchange network of n processors. Using O(n lg n) professors, the same algorithm can be pipelined to route α unicast assignments each involving O(k) pairs of inputs and outputs, in O(lg² k+lg n+(α-1) lg k) time on a completely connected network and in O(lg⁴ k+lg² k lg n+(α-1)(lg ³ k+lg k lg n)) time on the extended shuffle-exchange network. These yield an average routing time of O(lg k) in the first case, and O(lg³ k+1g k lg n) in the second case, for all α⩾lg n. These complexities indicate that the algorithm given in this paper is as fast as Nassimi and Sahni's algorithm for unicast assignments, and with pipelining, it is faster than the same algorithm at least by a factor of O(lg n) on both topologies. Furthermore, for sparse assignments, i.e., when k=O(1), it is the first algorithm which has an average routing time of O(1g n) on a topology with O(n) links     

Texture mapping using surface flattening via multidimensionalscaling

Presents a novel technique for texture mapping on arbitrary surfaces with minimal distortion by preserving the local and global structure of the texture. The recent introduction of the fast marching method on triangulated surfaces has made it possible to compute a geodesic distance map from a given surface point in O(n lg n) operations, where n is the number of triangles that represent the surface. We use this method to design a surface flattening approach based on multi-dimensional scaling (MDS). MDS is a family of methods that map a set of points into a finite-dimensional flat (Euclidean) domain, where the only data given is the corresponding distance between every pair of points. The MDS mapping yields minimal changes of the distances between the corresponding points. We then solve an "inverse" problem and map a flat texture patch onto a curved surface while preserving the structure of the texture     

平面点匹配的一点校准算法

点模式匹配是一项重要的视觉课题。对于一个平面点集,由平移和旋转并伴有一定噪声作用产生另一点集,提出一个基于一点校准的点模式快速匹配算法,并推广到带有属性点的匹配问题中。基于一点校准的点模式匹配算法,其计算复杂性为O(mn),其中m,n分别是两个点集所含点的个数,比基于两点距离近似相等的校准匹配算法,其计算复杂性为O(m2nl)(其中l为第二个点集中与第一个点集中任两个点的距离近似相等的平均个数),极大地减少了计算量。     

On computing all north-east nearest neighbors in the L1 metric

Given a collection of n points in the plane, we exhibit an algorithm that computes the nearest neighbor in the north-east (first quadrant) of each point, in the L₁ metric. By applying a suitable transformation to the input points, the same procedure can be used to compute the L₁ nearest neighbor in any given octant of each point. This is the basis of an algorithm for computing the minimum spanning tree of the n points in the L₁ metric. All three algorithms run in O(n lg n) total time and O(n) space.     

Fast agglomerative clustering using information of k-nearest neighbors

In this paper, we develop a method to lower the computational complexity of pairwise nearest neighbor (PNN) algorithm. Our approach determines a set of candidate clusters being updated after each cluster merge. If the updating process is required for some of these clusters, k-nearest neighbors are found for them. The number of distance calculations for our method is O(N²), where N is the number of data points. To further reduce the computational complexity of the proposed algorithm, some available fast search approaches are used. Compared to available approaches, our proposed algorithm can reduce the computing time and number of distance calculations significantly. Compared to FPNN, our method can reduce the computing time by a factor of about 26.8 for the data set from a real image. Compared with PMLFPNN, our approach can reduce the computing time by a factor of about 3.8 for the same data set.