二进制二维矩形分割算法

Question

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

任务可以通过截止日期和数据速率来识别，并且可以被视为二维图。看图:

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

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

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

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

Answer 1

根据给定的信息，您可以执行以下操作:

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

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

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

如果不是，则终止。

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