用一行劃分矩陣中的點

Question

可以說我有一個2D矩陣/地圖。在這個矩陣中，我放置了兩種類型的點（類型A，類型B）。我想知道，如果有可能用單一行將矩陣中的A型和B型點分開。我正在尋找算法或想法如何解決這個問題。任何建議appreiated。謝謝。

Answer 1

找到每個組的凸包（A型和B型），如果船體不相交，可以用直線將它們分開。

Answer 2

您在查找二進制文件linear classifier。

答案是肯定的當且僅當存在一個線性分類是一致與訓練組（即分類是給在訓練集中的每一個點，這是你的數據正確的標籤）。

Perceptron是一個簡單的方式實現一個線性分類器。 更高級的技術（這也是實現更好的分類器）是Support Vector Machine

Answer 3

這個問題有一個解決方案here描述一個非常好的O（n）的隨機算法。