如何在欧几里得空间中找到最远的邻居？

Question

给出2D中n个点的集合P，对于P中的任何点x，找出x最远邻居的最快方法是什么？最远的邻居是指P中与x的最大欧几里得距离的点。

Answer 1

据我所知，当前针对各种树（R树，四叉树，kd树）的标准kNN搜索算法是通过以下方法开发的：

G。 R. Hjaltason和H. Samet。，“空间中的距离浏览数据库。”，ACM TODS 24（2）：265--318。1999

请参见here。它基于最近节点/条目的优先级队列遍历树。 一个主要的见解是该算法也适用于最远的邻居搜索。

基本算法使用优先级队列。队列可以包含树节点以及数据条目，所有这些均按其到搜索点的距离排序。作为第一步，它将根节点添加到优先级队列中。然后重复以下步骤，直到找到k条目：

1. 从队列中获取第一个元素。如果它是一个条目，则将其返回。如果是节点，则将节点中的所有元素添加到优先级队列。
2. 重复1。

本文描述了R树的实现，但他们声称它可以应用于大多数树状结构。我自己用Java实现了R-Trees和PH-Trees（一种特殊的四叉树）的nearest邻居版本。我想我知道如何为KD-Trees有效地做到这一点，但我认为它有些复杂。