二元二维矩形分区算法

问题描述：

我们正在为异构计算做一个调度器。二元二维矩形分区算法

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

enter image description here

矩形标识任务安排在GPU上，外任务，在CPU上调度。

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

可以有高达20.000（点）的任务，并且轴可以任意长

是否有解决这个问题的任何已知的算法/数据结构？通过增加点最接近所有点的重心

开始：

有什么更多的标准是什么使一个良好的矩形？如果它只是“包含最多的任务”，那么最好的矩形就是一个包含所有20,000个点的矩形。 – Kevin

有一些资源约束（无论是否可以调度任务集）。确定点是否可以添加到矩形的函数表示这种关系。 – Sune1987

你在2d空间中绘制这个图很奇怪，并且没有任何标准来选择一个任务最适合的设备。我认为这个空间会有一条线或曲线将它分成两个区域，决定的是如何移动这条线。你画一个盒子，并有一个二进制结果进行一些评估...... – phkahler

答

在给定的信息，你可以做到以下几点。

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

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

如果不是，则终止。

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

简单而优雅的解决方案。谢谢 – Sune1987

答

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