查找图中的代表顶点

Question

对于计算机视觉中的某些项目，我有N高维空间中的点。我想选择其中将是“最可区分”彼此的k。例如，它可以翻译为所选点之间的距离总和最大。或者可以是多面体的体积最大。但通常任何有直觉的东西都可以去。

如预期的那样，我想找到这些代表性观点。

有两个问题：

• 为“最区分”点什么的定义是较常用的？他们是否改变了用于查找这些点的算法？
• 寻找点的算法是什么？它高度提醒我最大的加权集团问题。这是NP难题吗？在这种情况下，我们可以对最优解做出一些很好的近似？

Answer 1

你定义“最明显的”的方式肯定会影响你想要使用的算法。例如，您可以将“最可区分”定义为集合中任意两个点之间距离的最大总和，但您也可以将其定义为具有任意两个点之间最大最小距离的集合。这是两个完全不同的问题。

至于算法，正如我所说，这取决于你的定义。如果您想查找K最远的点，则应查看this question。这个问题是NP-Complete，但你可能会对如何解决这个问题有一些想法。