Выберите прямоугольники с максимальной площадью пересечения

В этой задаче r - фиксированное натуральное число. На плоскости даны N прямоугольников одинакового размера. Стороны бывают вертикальными или горизонтальными. Мы предполагаем, что область пересечения всех N прямоугольников имеет ненулевую площадь. Проблема в том, как найти N-r этих прямоугольников, чтобы максимизировать площадь пересечения. Эта проблема возникает в практической микроскопии, когда один многократно изображает данный биологический образец, и выравнивание немного изменяется во время этого процесса по физическим причинам (например, дифференциальное расширение частей микроскопа и камеры). Я выразил проблему для размерности d = 2. Аналогичная проблема возникает для каждого d> 0. Для d = 1 решение O (N log (N)) получается путем сортировки левых конечных точек интервалов. Но давайте придерживаться d = 2. Если r = 1, можно снова решить задачу за время O (N log (N)), отсортировав координаты углов.

Итак, исходная проблема решена путем решения сначала случая (N, 1) с получением N -1 прямоугольников, затем решая случай (N-1,1), получая N-2 прямоугольников и так далее, пока мы не уменьшим количество прямоугольников до Nr? Мне было бы интересно увидеть явный контрпример этой оптимистичной попытки процедуры. Было бы еще интереснее, если бы процедура работала (пожалуйста, докажите!), Но это кажется излишне оптимистичным.

Если r фиксируется на некотором значении r> 1, а N велико, эта проблема в одном из NP классы?

Спасибо за любые мысли по этому поводу.

Дэвид