n维[0,1]空间最远最近邻点求解算法及学术资源咨询

问题定义 #

给定n维[0, 1]范围内的点集，需要添加一个新点，使得该点到最近邻现有点的距离最大化，如何确定这个新点的位置？

示例说明 #

• 一维示例：给定点0、1、0.5、0.75，最优解为0.25，其最近邻为0和0.5，距离为0.25，无其他点能达到更大距离。
• 二维示例：给定点(0, 0)、(1, 0)、(0.75, 0)，最优解为(0.375, 1)，最近邻为(0, 0)和(0.75, 0)，距离约为1.068。
• 多解示例：给定点0.4、0.5、0.6，最优解为0和1，二者到最近邻的距离均为0.4。

实际场景与研究背景 #

• 实际场景：比如在岛屿上新建基站，选择最大无覆盖区域的深处部署，能有效提升信号覆盖范围。
• 研究背景：在研究生阶段的**案例库维护（Case-Base Maintenance，人工智能子领域）**研究中，将该问题应用于旅行社套餐案例库，新增套餐需要尽可能异于现有套餐，以此丰富案例库的多样性。

可用算法与学术资源 #

核心算法 #

1. Voronoi图相关算法
   该问题本质是寻找Voronoi图中的最远顶点，或者Voronoi区域内的最大内接球中心——在n维空间中，这些点就是到所有现有点的最近距离最大的位置。对于低维空间（如1、2、3维），可以通过构造Voronoi图，遍历所有Voronoi顶点和区域边界（包括空间边界）来找到最优解。
2. 全局优化算法
   对于高维空间，Voronoi图构造复杂度极高，可采用以下全局优化方法：
   • 遗传算法：通过迭代进化候选点，评估每个点的最近邻距离，保留最优个体进行交叉变异，逐步逼近最优解。
   • 模拟退火：通过随机搜索和概率性接受较差解的方式，避免陷入局部最优，适合高维非凸问题。
   • 粒子群优化：模拟群体智能，通过粒子间的信息共享调整搜索方向，高效寻找全局最优值。
3. 枚举与剪枝算法（低维场景）
   在1维场景中，可直接枚举所有相邻点的中点以及空间端点，计算每个点的最近邻距离，取最大值对应的点；2维场景可枚举Voronoi顶点、边的中点以及空间边界的极值点，逐一验证。

检索关键词 #

• 最远最近邻点问题（Farthest Nearest Neighbor Problem）
• 最大最小距离问题（Max-Min Distance Problem）
• Voronoi图 最远顶点（Farthest Voronoi Vertex）
• 案例库维护 多样性增强（Case-Base Maintenance Diversity Enhancement）
• 高维空间 最大最小距离优化（High-Dimensional Max-Min Distance Optimization）

推荐学术论文 #

1. "The Farthest Voronoi Diagram and Its Applications"：系统介绍了最远Voronoi图的构造方法及在空间优化问题中的应用，是该领域的经典基础文献。
2. "Max-Min Distance Design for Supervised Learning"：讨论了在机器学习场景下，如何通过最大化最小距离来选择样本点，其中的方法可迁移到案例库维护的场景中。
3. "Case-Base Maintenance: A Survey"：综述了案例库维护的核心问题与方法，其中包含关于案例多样性增强的相关策略，可结合最大最小距离问题进行拓展研究。
4. "Global Optimization Approaches for the Max-Min Distance Problem in High Dimensions"：针对高维空间的最大最小距离问题，对比了多种全局优化算法的性能，为高维场景的解决方案提供参考。

内容的提问来源于stack exchange，提问作者Brian Schack