我正在尝试编写一个空间数据结构（例如 aK-D tree或 a QuadTree），给定一个点，它将找到x最接近它的点。
我上面提到的数据结构的问题是它们主要支持径向/区域搜索。y因此，他们将获得给定点/节点半径内的点。
改变这些结构来搜索我想要的东西是低效的。我假设我需要多次重复径向搜索，从较短的径向距离开始，并不断增加它，直到我获得x接近给定点的所需点数。当然，这违背了数据结构背后的全部目的。
几乎所有的空间数据结构都在径向搜索上运行。我可以将哪些其他有效的搜索方法应用于 aQuadTree或我需要考虑的任何其他空间数据结构以实现我的意思？有什么建议么？
我不确定你的假设是否正确。关于 kd-trees的Wikipedia 文章指出了如何使用该结构来支持查找与x搜索点最近的邻居。是的，它本质上是重复寻找最近邻x时间，但我不确定您是否有权期望算法比kd-tree.
如果这对您来说还不够好，那么您可能需要将您的点存储在不同的数据结构中。如果x很小且有界，您可以将点存储在加权图中，其中边权重当然是点之间的距离。
如果x既不是小也不是有界的，您可以将空间简单地细分为k*m均匀的单元格（此处为 2D，如有必要，请膨胀至 3+D）。对于每个搜索点，直接进入包含它的单元格，找到同一单元格中的其他点。如果x它们中的一个比单元格的边界更靠近搜索点，那么这些就是您要查找的内容。如果没有，也请在附近边界另一侧的单元格中进行搜索。
如果您发现自己需要同时支持径向/区域搜索和x近邻搜索，那么如果您必须维护 2 个数据结构，一个来支持每种类型的查询，这并不是世界末日。对于许多搜索问题，有效解决方案的第一步是将数据放入正确的结构中以进行有效搜索。做出此决定取决于您根本没有提供给我们的数字。
如果您确实在四叉树上多次调用搜索方法（这是我已经做过几次的），那么如果您在每次调用时将搜索半径加倍，直到您获得正确的点数，搜索并不是那么低效.
假设一个 2d 空间，如果包含 X 点的正确最小半径是 R1，并且您继续加倍直到找到包含它们的半径 R2，那么 (a) R2 必须小于 2xR1 并且 (b) 搜索的区域每次搜索都会变大 4 倍，这（我认为）给你一个最坏的情况，你搜索过的区域只有一半实际上是不必要的（或大约）。