У нас есть прямоугольная сетка размером NxM, в которой каждая ячейка может быть либо свободной, либо занятой. Число или количество свободных ячеек намного больше числа занятых, поэтому мы представляем нашу сетку в виде списка координат XY занятых ячеек. Также мы предполагаем, что занятые клетки имеют определенную структуру.
Мы хотим найти самый большой прямоугольник, который охватывает только свободные ячейки. Далее мы хотим найти еще один самый большой прямоугольник, который должен не только покрывать только свободные ячейки, но и который не должен перекрываться с ранее найденными прямоугольниками. Мы хотим найти все такие прямоугольники до заданной пороговой области.
Другими словами, мы хотим найти прямоугольную мозаику, которая покрывает максимальную площадь свободных ячеек, используя жадный алгоритм.
Пример:
Входная сетка (0 - свободна, x - занята):
0 0 0 0 0
0 0 0 0 0
x 0 x 0 0
0 0 x 0 0
0 0 0 0 0
Решение (номера клеток обозначают прямоугольники решения):
1 1 1 1 1
1 1 1 1 1
x 0 x 2 2
3 3 x 2 2
3 3 0 2 2
Какие алгоритмы могут быть использованы для эффективного решения этой проблемы в вычислительном отношении? На первый взгляд следует использовать какой-то индекс (например, quadtree), чтобы получить практическую производительность для больших M и N (например, сотен тысяч). Решение не должно быть оптимальным, неоптимальным, но вычислительно эффективные подходы также хороши. Ссылки на академическую литературу приветствуются!
Бонусные баллы: обобщенный подход, применимый к 2D и 3D сеткам (и, возможно, даже к более высоким измерениям).