3

我正在寻找一种相当有效的算法（以及可能相关的数据结构）以在相当低的维度（d<10；通常 d=2 或 3）中完成以下任务：

给定一组（可能重叠！）球体和一个固定的边界框，我希望能够：

  1. 查询所述边界框中离任何球体 最远的点。
    1. 如果有多个这样的点，任意选择就可以了。
    2. 球体内的一点距离为零（也就是说，这些是球而不是空心球。）
    3. 如果每个点都在至少一个球内，那么在此处或 2.1. 处出错，或返回任意点都可以。
    4. 理想情况下，我正在寻找一个精确的（最多数值误差）解决方案；具有误差界限的收敛近似是可行的。
  2. 将新球体添加到集合中。
    1. 如果每个点现在至少在一个范围内，则在此处或 1.3 处出错。很好。

做一些初始预处理很好。

（请注意，球体可以重叠，并且可以具有不同的半径。）

（固定边界框，固定边界球，或者只是一个隐式凸包。任何一个都是可行的，以最简单的为准。）

乍一看，这与最大空球问题看似相似（您可以使用 Veronoi 图和一些处理来完成上述问题），但是从“要避免的点”到“要避免的球”的变化阻止了它的工作而且我还没有找到一个简单的扩展。

另一种似乎可行的方法是重复运行最大空球体问题，从每个球体中心点要避免的点开始，每次迭代将所有球体上的最近点添加到点集的当前解决方案中避免，但是这很昂贵并且没有明显的错误界限。

同上，我看着这个问题，然后说“这看起来像是你应该能够按摩 BSP 树去做的事情”，但我见过的大多数 BSP 算法倾向于更多地关注最近点，而不是最远点.

4

0 回答 0