低维下可重叠可变半径实心球的最远点查询及动态增球算法

核心问题本质拆解 #

你所定义的“距离所有实心球最远的点”，本质是在固定闭约束域Ω内，求解距离函数的全局最大值点：

距离函数定义为：点x到任意实心球的距离，取“点到球心的直线距离减去球半径”与0中的较大值；点x到整个球体集合的距离，取它到所有单个球距离中的最小值
这个函数的特性完全匹配**幂图（带权Voronoi）**的几何划分规则，不需要从零改造Voronoi图的适配逻辑。

最低实现成本的约束边界选择 #

直接优先选用**轴对齐固定边界框（AABB）**作为Ω，整体实现复杂度比固定边界球、任意凸包低60%以上：

• 无复杂凸几何预处理流程
• 所有解析求交点的计算都可以套用简单的边界约束公式
• 动态插入、边界覆盖检查的逻辑可以完全复用现有轴对齐包围盒的成熟实现

精确求解的理论依据（无额外数值误差） #

普通Voronoi图仅适用于零半径的点规避场景，而幂图从设计之初就是用来处理可变半径的带权空间划分的，完全匹配实心球的距离定义：

• 幂图的每个空间单元对应一个实心球，单元内的任意点到该球的带权距离，是所有球中最小的
• 原问题的精确解候选点不存在遗漏，一共仅三类：
  1. 幂图的内部顶点：即2维下由3个球、3维下由4个球共同确定的，与所有关联球外切、且不落入任何球内部的空点球心，这类点的f(x)值通常是全局最高的
  2. 幂图边/面与边界框的交点：即沿着幂图的边走到约束边界的位置，是内部无有效空点时的最优候选
  3. 边界框的顶点：即约束域的角点，是最极端的边界候选
• 计算逻辑完全匹配需求规则：只要点落入任意球内部，对应距离自动取0，不需要额外做覆盖判断
• 当所有候选点的f(x)值≤0时，即可判定边界域内所有点都被实心球覆盖，按规则抛出错误或返回任意点即可，无强制处理要求

静态预处理与首次最远点查询实现 #

初始状态下按以下流程做预处理，即可获得完全精确的查询结果：

• 对所有初始实心球，使用增量式Bowyer-Watson算法生成带权版本的三角剖分（即幂图），相比普通三角剖分仅需把距离计算替换为带权距离公式，实现逻辑改动极小
• 遍历所有幂图顶点、幂图与边界框的交点、边界框顶点，计算每个候选点对应的f(x)值
• 维护全局最大值记录，直接返回f(x)最高的候选点，整个过程无迭代、无收敛误差

动态新增球体的操作优化 #

不需要每次插入新球就全量重算幂图，完全复用三角剖分的增量插入逻辑即可：

• 新增球时，仅定位原幂图中所有被新球影响的空间单元（即带权距离大于新球带权距离的三角面）
• 删除受影响的旧单元，插入新球对应的空间单元，局部重新生成三角剖分——2/3维下，单个新球影响的单元数量平均为常数，不需要遍历全图
• 清理受影响区域的旧候选点，重新计算新生成的局部顶点、边界交点的f(x)值，更新全局最大值记录
• 每次插入完成后，检查全局最大值是否≤0，若是则判定全空间被覆盖，按规则抛出错误即可

带严格误差界的近似方案（适配高维/超大数量球的场景） #

当维度接近10、或球体数量过大导致幂图存储成本过高时，可切换为带严格误差保证的分支定界方案：

• 构建轴对齐层次包围盒树（2维四叉树/3维八叉树），把约束域Ω递归切分为层级化的子包围盒
• 对每个子包围盒，计算盒内可达f(x)的严格上界：上界 = min_i (盒子中心到第i个球的外切距离 - 盒子中心到盒内最远点的距离)
• 每次优先展开上界值最高的树节点，直到上界值与当前已知最优f(x)值的差小于设定的误差阈值ε——整个过程的误差是严格可验证的，不存在无界收敛问题
• 动态插入新球时，仅需更新所有树节点的f(x)上界即可，不需要重建树结构

已有思路的问题澄清 #

• 之前提到的“反复运行最大空点迭代”的思路，本质是把原问题简化为零权的点规避场景，每次迭代的解都是原问题的近似，没有解析上的收敛保证，计算成本远高于直接使用幂图的方案
• BSP树改造的思路存在冗余：幂图本身就是面向最近带权距离查询的高效空间划分结构，完全覆盖最远空点查询的所有候选点，不需要额外改造聚焦最近点查询的BSP树逻辑
• 幂图算法天生支持任意重叠、任意可变半径的实心球，不存在普通Voronoi处理重叠几何时的兼容问题

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