*ε*-NN in Possion Point Process

*q*、点集

*P*及近似参数$ \varepsilon $, 找到

*q*在

*P*中近似比不超过$ 1 + \varepsilon $的近似最近邻, 并提出了一个具有${\rm{O}}(\log n)$查询时间复杂度的图灵归约算法, 这里的查询时间是调用神谕的次数. 经过对比, 此时间优于所有现存的归约算法. 但是已发表文献中提出的归约算法的缺点在于, 其预处理时间和空间复杂度中有${\rm{O}}({(d/\varepsilon )^d})$的因子, 当维度数

*d*较大或者近似参数$ \varepsilon $较小时, 此因子将变得不可接受. 因此, 重新研究了该归约算法, 在输入点集服从泊松点过程的情况下, 分析算法的期望时间和空间复杂度, 将算法的期望预处理时间复杂度降到${\rm{O}}(n\log n)$, 期望空间复杂度降到${\rm{O}}(n\log n)$, 而期望查询时间复杂度保持${\rm{O}}(\log n)$不变, 从而完成了在已发表文献中所提出的未来工作.

*ε*-NN is studied. In other words, given a query point

*q*, a point set

*P*, and an approximate factor

*ε*, the purpose is to return the approximate nearest neighbor of

*q*in

*P*with an approximation ratio of not more than 1+

*ε*. Moreover, a Turing reduction algorithm with O(log

*n*) query time complexity is proposed, where the query time is the number of times that the oracle is invoked. The comparison indicates that the O(log

*n*) query time is the lowest compared to that of all the existing algorithms. However, the disadvantage of the proposed algorithm is that there is a factor of O((

*d*/

*ε*)

*) in the preprocessing time complexity and space complexity. When the number of dimensions*

^{d}*d*is high, or the approximation factor

*ε*is small, the factor would become unacceptable. Therefore, this study revises the reduction algorithm and analyzes the expected time complexity and space complexity of the algorithm when the input point set follows the Poisson point process. As a result, the expected preprocessing time complexity is reduced to O(

*n*log

*n*), and the expected space complexity is reduced to O(

*n*log

*n*), while the expected query time complexity remains O(log

*n*). In this sense, the future work raised in the published study is completed.