algorithm - 如何以规则的密度选择点

Question

如何选择具有规则密度的点子集？更正式地说，

给定

1. 一组 A 不规则间隔的点，
2. 距离度量 dist (例如，欧氏距离)，
3. 和目标密度d，

如何选择满足以下条件的最小子集B？

• 对于A中的每个点x，
• 在B中存在一个点y
• 满足dist(x,y) <= d

我目前最好的办法是

• 从A本身开始
• 挑选出最接近(或特别接近)的几个点
• 随机排除其中一个
• 只要条件成立就重复

并重复整个过程以获得好运。但是还有更好的方法吗？

我正在尝试用 280,000 个 18-D 点来做到这一点，但我的问题是一般策略。所以我也想知道如何用二维点来做。而且我真的不需要保证最小的子集。欢迎使用任何有用的方法。谢谢。

---

自下而上的方法

• 随机选择一个点
• 在未选择的 y 中选择为此 min(d(x,y) for x in selected)是最大的
• 继续前进!

我将其称为自下而上，而我最初发布的是自上而下。这在开始时要快得多，所以对于稀疏采样这应该更好？

绩效衡量

如果不需要保证最优性，我认为这两个指标可能会有用:

• 覆盖半径:max {y in unselected} min(d(x,y) for x in selected)
• 经济半径:min {y in selected != x} min(d(x,y) for x in selected)

RC 是允许的最小 d，这两者之间没有绝对的不平等。但是RC <= RE更可取。

我的小方法

为了演示该“性能度量”，我生成了 256 个均匀分布或按标准正态分布分布的二维点。然后我用它们尝试了自上而下和自下而上的方法。这就是我得到的:

RC 是红色，RE 是蓝色。 X 轴是所选点的数量。你认为自下而上也一样好吗？看动画的时候我是这么认为的，但似乎自上而下要好得多(看看稀疏区域)。尽管如此，考虑到它的速度要快得多，也不算太糟糕。

我在这里打包了所有东西。

http://www.filehosting.org/file/details/352267/density_sampling.tar.gz

Answer 1

你可以用图来模拟你的问题，假设点为节点，如果两个节点的距离小于d，则用边连接两个节点，现在你应该找到最小的顶点数，使得它们是它们连接的顶点覆盖了图的所有节点，这是minimum vertex cover problem (这通常是 NP-Hard)，但您可以使用快速 2 近似:重复将边的两个端点放入顶点覆盖中，然后将它们从图中移除。

P.S:确保您应该选择与图形完全断开连接的节点，在删除这些节点(意味着选择它们)之后，您的问题是顶点覆盖。