二元二維矩形分區算法

Question

我們正在爲異構計算做一個調度器。

任務可以通過他們的截止日期和他們的數據速率來識別，並可以被視爲一個二維圖。見圖片：

矩形標識任務安排在GPU上，外任務，在CPU上調度。

問題是我們想要高效地識別用於創建最佳矩形的參數。即包含大多數任務的矩形。可以假定確定是否可以將點添加到當前矩形的功能。

可以有高達20.000（點）的任務，並且軸可以任意長

是否有解決這個問題的任何已知的算法/數據結構？通過增加點最接近所有點的重心

開始：

Answer 1

在給定的信息，你可以做到以下幾點。

如果已添加n個點，請選擇最接近當前矩形的點作爲第n + 1個點。詢問你的給定函數，是否可以添加這個點。

如果是這樣，膨脹矩形，使其包含此點。假設所有的點都有獨特的x和y座標，總是可以在矩形中添加一個點。

如果不是，則終止。

如果這不是你想要的，請提供更多信息。

Answer 2

如果您的意思是一個層次聚類，您可以使用空間索引或空間填充曲線來細分象限中的二維圖。象限可以表示線程或核心。然後，您需要使用此功能對點進行排序，並檢查點數最多的象限。