最大化 3D 中具有距离约束的点的总和

Question

问题

问题陈述如下，给定 3D 中的一组点

p_i

，以及它们对应的能量值

e_i

，找到它们的一个子集，其中它们的能量总和最大化，并且每个点之间的距离两个选定点大于常数

。

这些是我迄今为止的想法的总结，我认为这些是有帮助的，但可能会产生误导。

贪婪算法：按能量值对点进行排序，这不能保证给出最佳答案。
概括问题：图模型，我创建了一个图，其中每个顶点代表一个点，并且两个点当且仅当它们足够近（它们的距离小于r）时才连接。现在的目标是选择一个独立的集合来最大化能量函数。现在问题是 NP 困难的（独立集问题简化为，将
```
e_i
```
s 设置为 1），这意味着，如果我不使用点的空间属性并假设空间度量是一个完全任意的函数，那么问题就无法解决了。
知道这一点后，我尝试解决一维问题，其中点位于一条线上，并且我做到了。按
```
x
```
值对点进行排序后，让
```
dp[i][j]
```
表示当我们仅使用第一个
```
i
```
点时问题的答案，同时遵守额外的约束：每个
```
x_k
```
之间的距离 (k < i) and
```
x_j
```
必须小于
```
r
```
。这意味着我们想要解决第一个
```
i
```
元素的问题，同时仍然有可能选择之后的
```
x_j
```
。可以根据这个公式构建动态规划算法。

我发现3.和2.之间的区别在于，当我们对点进行排序时，如果例如

p_1

和

p_2

没有冲突，那么

p_1

和

p_i

、

i > 2

不冲突。根本不冲突（我所说的冲突是指比

更接近）。恰恰：在每个

i, j, k; i < j < k

的排序数组中，我们有

p_i < p_j < p_k

，因此

p_j - p_i > r

结果

p_k - p_i > r

。我认为这就是造成差异的原因，并将复杂性从 NP-Hard 降低到

O(n^2)

我试图概括我对 2D 情况的答案，但我陷入困境，首先我尝试按点与原始点的距离对点进行排序，这不满足上述属性，然后我再次尝试按它们的径向角度排序发现自己不够聪明

我对计算几何了解不多，但我觉得答案就隐藏在其中使用的一些技术背后。

这是视觉任务的一个子问题，为了避免任何 XY 问题，我也会解释原来的问题，即使我可能会使这个特定的子问题复杂化，我发现它很有趣，并且会感谢任何帮助。

最初的问题：假设我有一个物体位于已知标记图案（ArUco Board）上的视频，我可以使用它找到相机变换。我想从物体表面计算点云。我可以使用每一帧并计算矩阵

，然后将图像与其他图像进行匹配，但首先，时间复杂度很烦人，其次，大多数帧彼此非常接近，我们知道低视差会导致更高的误差。最后，一些图像由于运动而变得模糊。

所以我想，我可以计算标记的重投影误差作为指示帧有多好的一个因素，并设置选择用于匹配和表面提取的帧之间的最小距离。

Answer 1

这是此问题的混合整数规划模型：

有 100 个点，随机位置，随机能量水平，mindist=50，我得到：

----     42 VARIABLE x.L  selected points

point7  1,    point15 1,    point22 1,    point50 1,    point89 1

优化花费了 0 秒（使用良好的 MIP 求解器）。