This paper studies the emergent dynamics of a flock with nonlinear inherent dynamics under closest neighbors model.We establish sufficient frameworks for convergence to flocking in terms of initial state and system pa...This paper studies the emergent dynamics of a flock with nonlinear inherent dynamics under closest neighbors model.We establish sufficient frameworks for convergence to flocking in terms of initial state and system parameters.When the number of closest neighbors is at least half of the population,it is shown that convergence to flocking occurs regardless of the initial state provided that the Lipschitz constant of nonlinear dynamics is smaller than the coupling strength.In contrast,when this number of closest neighbors is less than half of the population,we need to impose some restrictive conditions on the initial state to ensure the emergence of flocking based on the disturbed graphs approach.Our results are applicable to both continuous and discrete time cases.Finally,the validity of our theoretical analysis is tested by numerical simulations.展开更多
In this paper, constrained K closest pairs query is introduced, wbich retrieves the K closest pairs satisfying the given spatial constraint from two datasets. For data sets indexed by R trees in spatial databases, thr...In this paper, constrained K closest pairs query is introduced, wbich retrieves the K closest pairs satisfying the given spatial constraint from two datasets. For data sets indexed by R trees in spatial databases, three algorithms are presented for answering this kind of query. Among of them, two-phase Range＋Join and Join＋Range algorithms adopt the strategy that changes the execution order of range and closest pairs queries, and constrained heap-based algorithm utilizes extended distance functions to prune search space and minimize the pruning distance. Experimental results show that constrained heap-base algorithm has better applicability and performance than two-phase algorithms.展开更多
The iterative closest point(ICP)algorithm has the advantages of high accuracy and fast speed for point set registration,but it performs poorly when the point set has a large number of noisy outliers.To solve this prob...The iterative closest point(ICP)algorithm has the advantages of high accuracy and fast speed for point set registration,but it performs poorly when the point set has a large number of noisy outliers.To solve this problem,we propose a new affine registration algorithm based on correntropy which works well in the affine registration of point sets with outliers.Firstly,we substitute the traditional measure of least squares with a maximum correntropy criterion to build a new registration model,which can avoid the influence of outliers.To maximize the objective function,we then propose a robust affine ICP algorithm.At each iteration of this new algorithm,we set up the index mapping of two point sets according to the known transformation,and then compute the closed-form solution of the new transformation according to the known index mapping.Similar to the traditional ICP algorithm,our algorithm converges to a local maximum monotonously for any given initial value.Finally,the robustness and high efficiency of affine ICP algorithm based on correntropy are demonstrated by 2D and 3D point set registration experiments.展开更多
For localisation of unknown non-cooperative targets in space,the existence of interference points causes inaccuracy of pose estimation while utilizing point cloud registration.To address this issue,this paper proposes...For localisation of unknown non-cooperative targets in space,the existence of interference points causes inaccuracy of pose estimation while utilizing point cloud registration.To address this issue,this paper proposes a new iterative closest point(ICP)algorithm combined with distributed weights to intensify the dependability and robustness of the non-cooperative target localisation.As interference points in space have not yet been extensively studied,we classify them into two broad categories,far interference points and near interference points.For the former,the statistical outlier elimination algorithm is employed.For the latter,the Gaussian distributed weights,simultaneously valuing with the variation of the Euclidean distance from each point to the centroid,are commingled to the traditional ICP algorithm.In each iteration,the weight matrix W in connection with the overall localisation is obtained,and the singular value decomposition is adopted to accomplish high-precision estimation of the target pose.Finally,the experiments are implemented by shooting the satellite model and setting the position of interference points.The outcomes suggest that the proposed algorithm can effectively suppress interference points and enhance the accuracy of non-cooperative target pose estimation.When the interference point number reaches about 700,the average error of angle is superior to 0.88°.展开更多
The numbers of local complimentary inequivalent graph states for 9, 10 and 11 qubit systems are 440, 3132, 40457, respectively. We calculate the entanglement, the lower and upper bounds of the entanglement and obtain ...The numbers of local complimentary inequivalent graph states for 9, 10 and 11 qubit systems are 440, 3132, 40457, respectively. We calculate the entanglement, the lower and upper bounds of the entanglement and obtain the closest product states for all these graph states. New patterns of closest product states are analyzed.展开更多
Background There are many regularly shaped objects in artificial environments.It is difficult to distinguish the poses of these objects when only geometric information is used.With the development of sensor technologi...Background There are many regularly shaped objects in artificial environments.It is difficult to distinguish the poses of these objects when only geometric information is used.With the development of sensor technologies,inclusion of other information can be used to solve this problem.Methods We propose an algorithm to register point clouds by integrating color information.The key idea of the algorithm is to jointly optimize the dense and edge terms.The dense term was built in a manner similar to that of the iterative closest point algorithm.To build the edge term,we extracted the edges of the images obtained by projecting point clouds.The edge term prevents the point clouds from sliding during registration.We used this loosely coupled method to fuse geometric and color information.Results The results of the experiments showed that the edge image approach improves precision,and the algorithm is robust.展开更多
THREE months after the operation that gave her an artificial trachea, Mi Aiyun was able to breathe normally, and fit enough to work in the fields for three to four hours. On July 26, 2002, Zhao Fengrui, designer of th...THREE months after the operation that gave her an artificial trachea, Mi Aiyun was able to breathe normally, and fit enough to work in the fields for three to four hours. On July 26, 2002, Zhao Fengrui, designer of the artificial trachea and main operating surgeon, announced that his was the world’s first tracheal prosthesis capable of integrating completely with the human trachea.Six years ago, Mi Aiyun, a 48-year-old展开更多
As early as in 1975, Shamos and Hoey first gave an O（n lg n）-time divide-and-conquer algorithm （Stt algorithm in short） for the problem of finding the closest pair of points. In one process of combination, the Euc...As early as in 1975, Shamos and Hoey first gave an O（n lg n）-time divide-and-conquer algorithm （Stt algorithm in short） for the problem of finding the closest pair of points. In one process of combination, the Euclidean distances between 3n pairs of points need to be computed, so the overall complexity of computing distance is then 3n lgn. Since the computation of distance is more costly compared with other basic operation, how to improve SH algorithm from the aspect of complexity of computing distance is considered. In 1998, Zhou, Xiong and Zhu improved SH algorithm by reducing this complexity to 2n lg n. In this paper, we make further improvement. The overall complexity of computing distances is reduced to （3n lg n）/2, which is only half that of SH 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...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.展开更多
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 pairwi...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 25-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 lgn）, the reduction in the total number of comparisons leads to a significant reduction in the total execution time, for inputs with size sufficiently large.展开更多
Given an n-dimensional lattice L and some target vector, this paper studies the algorithms for approximate closest vector problem （CVPγ） by using an approximate shortest independent vectors problem oracle （SIVPγ...Given an n-dimensional lattice L and some target vector, this paper studies the algorithms for approximate closest vector problem （CVPγ） by using an approximate shortest independent vectors problem oracle （SIVPγ）. More precisely, if the distance between the target vector and the lattice is no larger than c/γn λ1（L） for arbitrary large but finite constant c 〉 0, we give randomized and deterministic polynomial time algorithms to find a closest vector, while previous reductions were only known for 1/2γn λ1（L）. Moreover, if the distance between the target vector and the lattice is larger than some quantity with respect to λn（L）, using SIVPγ oracle and Babai＇s nearest plane algorithm, we can solve CVPγ√n in deterministic polynomial time. Specially, if the approximate factor γ ∈ （1, 2） in the SIVPγ oracle, we obtain a better reduction factor for CVP.展开更多
Affine ellipses/ellipsoids based bounding volumes are widely used in various graphics applications,such as ray tracing and collision detection.They provide a much tighter fit than the regular ellipses/ellipsoids.The m...Affine ellipses/ellipsoids based bounding volumes are widely used in various graphics applications,such as ray tracing and collision detection.They provide a much tighter fit than the regular ellipses/ellipsoids.The most important operation involved is to compute the closest/farthest point,on a given ellipse/ellipsoid,with respect to a user specified point.In this paper,we first formulate such a problem for the ellipse case into solving a quartic equation and then for the ellipsoid case by solving a system of quartic equations.The method proposed in this paper is elegant and highly efficient.展开更多
基金supported by the National Key R&D Program of China(2023YFA1009200)the National Natural Science Foundation of China(12171069)the Fundamental Research Funds for the Central Universities.
文摘This paper studies the emergent dynamics of a flock with nonlinear inherent dynamics under closest neighbors model.We establish sufficient frameworks for convergence to flocking in terms of initial state and system parameters.When the number of closest neighbors is at least half of the population,it is shown that convergence to flocking occurs regardless of the initial state provided that the Lipschitz constant of nonlinear dynamics is smaller than the coupling strength.In contrast,when this number of closest neighbors is less than half of the population,we need to impose some restrictive conditions on the initial state to ensure the emergence of flocking based on the disturbed graphs approach.Our results are applicable to both continuous and discrete time cases.Finally,the validity of our theoretical analysis is tested by numerical simulations.
基金Supported by National Natural Science Foundationof China (60073045)
文摘In this paper, constrained K closest pairs query is introduced, wbich retrieves the K closest pairs satisfying the given spatial constraint from two datasets. For data sets indexed by R trees in spatial databases, three algorithms are presented for answering this kind of query. Among of them, two-phase Range＋Join and Join＋Range algorithms adopt the strategy that changes the execution order of range and closest pairs queries, and constrained heap-based algorithm utilizes extended distance functions to prune search space and minimize the pruning distance. Experimental results show that constrained heap-base algorithm has better applicability and performance than two-phase algorithms.
基金supported in part by the National Natural Science Foundation of China(61627811,61573274,61673126,U1701261)
文摘The iterative closest point(ICP)algorithm has the advantages of high accuracy and fast speed for point set registration,but it performs poorly when the point set has a large number of noisy outliers.To solve this problem,we propose a new affine registration algorithm based on correntropy which works well in the affine registration of point sets with outliers.Firstly,we substitute the traditional measure of least squares with a maximum correntropy criterion to build a new registration model,which can avoid the influence of outliers.To maximize the objective function,we then propose a robust affine ICP algorithm.At each iteration of this new algorithm,we set up the index mapping of two point sets according to the known transformation,and then compute the closed-form solution of the new transformation according to the known index mapping.Similar to the traditional ICP algorithm,our algorithm converges to a local maximum monotonously for any given initial value.Finally,the robustness and high efficiency of affine ICP algorithm based on correntropy are demonstrated by 2D and 3D point set registration experiments.
基金supported by the National Natural Science Foundation of China(51875535)the Natural Science Foundation for Young Scientists of Shanxi Province(201901D211242201701D221017)。
文摘For localisation of unknown non-cooperative targets in space,the existence of interference points causes inaccuracy of pose estimation while utilizing point cloud registration.To address this issue,this paper proposes a new iterative closest point(ICP)algorithm combined with distributed weights to intensify the dependability and robustness of the non-cooperative target localisation.As interference points in space have not yet been extensively studied,we classify them into two broad categories,far interference points and near interference points.For the former,the statistical outlier elimination algorithm is employed.For the latter,the Gaussian distributed weights,simultaneously valuing with the variation of the Euclidean distance from each point to the centroid,are commingled to the traditional ICP algorithm.In each iteration,the weight matrix W in connection with the overall localisation is obtained,and the singular value decomposition is adopted to accomplish high-precision estimation of the target pose.Finally,the experiments are implemented by shooting the satellite model and setting the position of interference points.The outcomes suggest that the proposed algorithm can effectively suppress interference points and enhance the accuracy of non-cooperative target pose estimation.When the interference point number reaches about 700,the average error of angle is superior to 0.88°.
文摘The numbers of local complimentary inequivalent graph states for 9, 10 and 11 qubit systems are 440, 3132, 40457, respectively. We calculate the entanglement, the lower and upper bounds of the entanglement and obtain the closest product states for all these graph states. New patterns of closest product states are analyzed.
文摘Background There are many regularly shaped objects in artificial environments.It is difficult to distinguish the poses of these objects when only geometric information is used.With the development of sensor technologies,inclusion of other information can be used to solve this problem.Methods We propose an algorithm to register point clouds by integrating color information.The key idea of the algorithm is to jointly optimize the dense and edge terms.The dense term was built in a manner similar to that of the iterative closest point algorithm.To build the edge term,we extracted the edges of the images obtained by projecting point clouds.The edge term prevents the point clouds from sliding during registration.We used this loosely coupled method to fuse geometric and color information.Results The results of the experiments showed that the edge image approach improves precision,and the algorithm is robust.
文摘THREE months after the operation that gave her an artificial trachea, Mi Aiyun was able to breathe normally, and fit enough to work in the fields for three to four hours. On July 26, 2002, Zhao Fengrui, designer of the artificial trachea and main operating surgeon, announced that his was the world’s first tracheal prosthesis capable of integrating completely with the human trachea.Six years ago, Mi Aiyun, a 48-year-old
基金This work is supported by the National Natural Science Foundation of China （Grant No. 60496321） and Shanghai Science and Technology Development Fund （Grant No. 025115032）.
文摘As early as in 1975, Shamos and Hoey first gave an O（n lg n）-time divide-and-conquer algorithm （Stt algorithm in short） for the problem of finding the closest pair of points. In one process of combination, the Euclidean distances between 3n pairs of points need to be computed, so the overall complexity of computing distance is then 3n lgn. Since the computation of distance is more costly compared with other basic operation, how to improve SH algorithm from the aspect of complexity of computing distance is considered. In 1998, Zhou, Xiong and Zhu improved SH algorithm by reducing this complexity to 2n lg n. In this paper, we make further improvement. The overall complexity of computing distances is reduced to （3n lg n）/2, which is only half that of SH algorithm.
基金This work is partially supported by Utah State University under Grant No.A13501.
文摘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.
文摘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 25-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 lgn）, the reduction in the total number of comparisons leads to a significant reduction in the total execution time, for inputs with size sufficiently large.
基金This work is partially supported by the National Basic Research 973 Program of China under Grant No. 2011CB302400, the National Natural Science Foundation of China under Grant Nos. 61379139 and 61133013, and the Strategic Priority Research Program of the Chinese Academy of Sciences under Grant No. XDA06010701.
文摘Given an n-dimensional lattice L and some target vector, this paper studies the algorithms for approximate closest vector problem （CVPγ） by using an approximate shortest independent vectors problem oracle （SIVPγ）. More precisely, if the distance between the target vector and the lattice is no larger than c/γn λ1（L） for arbitrary large but finite constant c 〉 0, we give randomized and deterministic polynomial time algorithms to find a closest vector, while previous reductions were only known for 1/2γn λ1（L）. Moreover, if the distance between the target vector and the lattice is larger than some quantity with respect to λn（L）, using SIVPγ oracle and Babai＇s nearest plane algorithm, we can solve CVPγ√n in deterministic polynomial time. Specially, if the approximate factor γ ∈ （1, 2） in the SIVPγ oracle, we obtain a better reduction factor for CVP.
基金Supported by the National Natural Science Foundation of China(No.60933007)
文摘Affine ellipses/ellipsoids based bounding volumes are widely used in various graphics applications,such as ray tracing and collision detection.They provide a much tighter fit than the regular ellipses/ellipsoids.The most important operation involved is to compute the closest/farthest point,on a given ellipse/ellipsoid,with respect to a user specified point.In this paper,we first formulate such a problem for the ellipse case into solving a quartic equation and then for the ellipsoid case by solving a system of quartic equations.The method proposed in this paper is elegant and highly efficient.
