对于一些计算机视觉项目，我在高维空间中有 N 个点。我想从中选出 k 个“最容易区分”的。例如，它可以转化为所选点之间的距离总和最大。或者也可以是多面体的体积最大。但一般来说，任何背后有一些直觉的东西都可以。
果然是想找到这些有代表性的点。
有两个问题:
- 更常用的“最明显”点的定义是什么？他们是否更改了用于查找这些点的算法？
- 找到点的算法是什么？它高度提醒我最大加权集团问题。是NP难问题吗？在这种情况下，我们能否对最优解做出一些好的近似？
最佳答案
您定义“最有区别”的方式肯定会影响您要使用的算法。例如，您可以将“最可区分的”定义为集合中任意两点之间的距离之和最大的集合，但您也可以将其定义为任意两点之间的最大最小距离的集合。这是两个完全不同的问题。
至于算法，正如我所说，这取决于您的定义。如果你想找到 K 最远的点，你应该看看 this question .这个问题是 NP 完全问题，但您可能会对如何解决这个问题有一些想法。
关于algorithm - 在图中查找代表性顶点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21831864/