二维矩形分块的算法

Question

我们正在做一个异构计算的调度器。

可以通过任务的截止期和数据速率来识别任务，并可以将其视为二维图。请参见图像：

​

​

矩形标识要在GPU上调度的任务，以及要在CPU上调度的外部任务。

问题是我们想要有效地识别创建最佳矩形的参数。即包含最多任务的矩形。可以假定存在确定是否可以将点添加到当前矩形的函数。

最多可以有20.000个(点)任务，轴可以是任意长度

是否有任何已知的算法/数据结构可以解决此问题？

Answer 1

使用给定的信息，您可以执行以下操作：

首先添加离所有点的重心最近的点。

如果已经添加了n个点，请选择作为n+1st点，这是最接近当前矩形的点。询问你给定的函数，这个点是否可以添加。

如果是这样的话，膨胀这个矩形，使它包含这个点。假设所有的点都有唯一的x和y坐标，总是可以只向矩形中添加一个点。

如果不是，则终止。

如果这不是您想要的，请提供更多信息。

Answer 2

如果您指的是分层集群，则可以使用空间索引或空间填充曲线将2d图细分为象限。象限可以表示线程或核心。然后，您需要使用此函数对点进行排序，并检查具有最多点的象限。