オーバーラップせずに一連の長方形をカバーする最も少ない長方形を見つけるためのアルゴリズム

Question

一連の長方形があり、セットを「削減」したいので、元のセットと同じ領域を記述するための長方形の数が最も少ないです。可能であれば、私もそれを速くしたいと思っていますが、私は長方形の数を可能な限り低くすることにもっと関心があります。ほとんどの場合動作するアプローチがあります。

現在、私は最も長い左の左から始めて、長方形を維持しながら右下を拡張できるかどうかを確認します。拡張できなくなるまでそれを行い、交差するすべての長方形を削除して分割し、リストに拡張された長方形を戻します。次に、次の左上の最も長方形などで再びプロセスを開始します。しかし、場合によっては機能しません。例えば：

この3つの長方形のセットを使用すると、正しいソリューションは次のように2つの長方形になります。

ただし、この場合、私のアルゴリズムは青い長方形を処理することから始まります。これにより、下方に拡張し、黄色の長方形が（正しく）分割されます。しかし、その後、黄色の長方形の残りの部分が処理されると、最初に拡張するのではなく、最初に拡張し、以前に分割された部分を取り戻します。その後、最後の長方形が処理され、右または下に拡張できないため、元の長方形のセットが残ります。アルゴリズムを微調整して、最初に拡張し、次に右に拡張することができました。これにより、このケースが修正されますが、反転した同様のシナリオで同じ問題が発生します。

編集： 明確にするために、元の長方形のセットは重複せず、接続する必要はありません。また、長方形のサブセットが接続されている場合、それらを完全に覆うポリゴンには穴があります。