алгоритм двоичного двумерного прямоугольного разбиения

Question

Мы делаем планировщик для гетерогенных вычислений.

Задачи могут быть определены по срокам и скорости передачи данных и могут рассматриваться как двумерный график. Смотрите изображение:

Прямоугольник определяет задачи, которые должны быть запланированы на GPU, и внешние задачи, которые должны быть запланированы на CPU.

Проблема в том, что мы хотим эффективно определить параметры для создания наилучшего прямоугольника. То есть прямоугольник, содержащий большинство задач. Можно предположить, что функция, определяющая, может ли точка быть добавлена ​​к текущему прямоугольнику, присутствует.

Может быть до 20 000 (точек) задач, а длина оси может быть произвольной

Существуют ли известные алгоритмы / структуры данных, решающие эту проблему?

Answer 1

Если вы имеете в виду иерархический кластер, вы можете использовать пространственный индекс или кривую заполнения пространства для разделения 2-го графа на квадранты.Квадрант может представлять поток или ядро.Затем вам нужно отсортировать точки с помощью этой функции и проверить квадрант с наибольшим количеством точек.

Answer 2

Используя данную информацию, вы можете сделать следующее:

Начните с добавления точки, ближайшей к центру тяжести всех точек.

Если уже добавлено n точеквыберите n + 1-ую точку, ближайшую к текущему прямоугольнику.Спросите заданную функцию, можно ли добавить эту точку.

Если это так, надуйте прямоугольник, чтобы он содержал эту точку.Предполагая, что все точки имеют уникальные координаты x и y, всегда можно добавить только одну точку к прямоугольнику.

Если нет, завершить.

Если это не то, что вы хотите, дайтебольше информации.