algorithm - 二元二维矩形分割算法

Question

我们正在为异构计算做一个调度程序。

这些任务可以通过它们的截止日期和它们的数据速率来识别，并且可以被视为一个二维图。见图片：

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

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

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

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

Answer 1

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

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

如果已经添加了 n 个点，则选择 n+1st 点，即离当前矩形最近的点。询问您给定的功能，是否可以添加此点。

如果是这样，膨胀矩形使其包含这个点。假设所有点都具有唯一的 x 和 y 坐标，则始终可以只向矩形添加一个点。

如果不是，则终止。

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

Answer 2

如果您的意思是分层集群，您可以使用空间索引或空间填充曲线将二维图细分为象限。一个象限可以代表一个线程或一个核心。然后您需要使用此功能对点进行排序并检查点最多的象限。