查找圖中的代表頂點

Question

對於計算機視覺中的某些項目，我有N高維空間中的點。我想選擇其中將是「最可區分」彼此的k。例如，它可以翻譯爲所選點之間的距離總和最大。或者可以是多面體的體積最大。但通常任何有直覺的東西都可以去。

如預期的那樣，我想找到這些代表性觀點。

有兩個問題：

• 爲「最區分」點什麼的定義是較常用的？他們是否改變了用於查找這些點的算法？
• 尋找點的算法是什麼？它高度提醒我最大的加權集團問題。這是NP難題嗎？在這種情況下，我們可以對最優解做出一些很好的近似？

Answer 1

你定義「最明顯的」的方式肯定會影響你想要使用的算法。例如，您可以將「最可區分」定義爲集合中任意兩個點之間距離的最大總和，但您也可以將其定義爲具有任意兩個點之間最大最小距離的集合。這是兩個完全不同的問題。

至於算法，正如我所說，這取決於你的定義。如果您想查找K最遠的點，則應查看this question。這個問題是NP-Complete，但你可能會對如何解決這個問題有一些想法。