Near-Neighbor Algorithms for Processing Bearing Data

摘要

The authors discuss the use of near-neighbor algorithms for correlating sets of tracks and sensor data on large numbers of rapidly moving objects. By investigating the scaling of such algorithms with the numbers of elements in the data sets, one finds that near-neighbor algorithms need not be universally more cost-effective than brute force methods. While the data access time of near-neighbor techniques scales with the number of objects N better than brute force, the cost of setting up the data structure could scale worse than brute force by a multiplicative factor of log N in an extreme case. For cases in which near-neighbor algorithms are advantageous, the authors describe how such techniques could be used to correlate three-dimensional tracks with bearing data recorded as two angles (theta, phi) from a single sensor. The paper then presents a high-speed algorithm for fusing bearing data from three or more sensors with overlapping fields of view in order to obtain the three-dimensional positions of the objects being observed. The algorithm permits the use of near-neighbor techniques, reducing the scaling of the problem from N to the m power to NlnN, where N is the number of objects in the common domain of observation, and m is the number of sensors involved. Numerical tests indicate the relative efficiencies of typical near-neighbor techniques in solving the multisensor angle-to-position fusion problem. Keywords: Passive sensors. (FR)