2011-12-14 51 views
3

2D軸上にN個の接続線のセットがあれば、Xの最小境界矩形を決定するアルゴリズムを探しています。一連の線の境界線の矩形を見つけるにはどうすればよいですか?

例えば、私は10行が与えられているとしますが、私は最大3つの(潜在的に交差する)長方形でそれらを束縛したいとします。したがって、ラインのうち8つが密接にクラスタリングされている場合は、1つの矩形を使用し、他の2つは、互いに近接しているので、第2の矩形またはおそらくは第3の矩形を使用することがあります。

ありがとうございました。

+1

申し訳ありませんが、私は最小限に抑えたいものを得られませんでした:長方形の数?長方形の集約領域?他に何か? – Miquel

+0

集約領域。混乱させて申し訳ありません。 – glutz

+0

余分な情報をありがとう。しかし、私はそれを考えていますが、より多くの制限が必要な場合や、各点の周りに極小の矩形を作成するだけでよい場合は、 – Miquel

答えて

2

実際に行がパスである場合、各矩形がパスの連続部分をカバーするという要件を嫌うことはないでしょう。この場合、時間O(n r)で実行される動的プログラムがあります.nはセグメント数、rは長方形の数です。

エントリC(i、j)がセグメント1、...、iをj個の長方形でカバーするコストを表すテーブルを計算する。再発は、iについて、であり、J> 0、

C(0、0)= 0
C(iは0)=∞
i「はC(i、j)は=分かけ< I

O(nr)個のエントリがあり、それぞれが時間内に計算されます(O(n-1)、O(n-1)に)。最後に、例えば、各エントリについて最良のi 'を記憶することによって、矩形の最適な集合を復元する。

一般的なケースでは、単純で最適なアルゴリズムはわかりません。 「唯一の」O(n )の矩形があり、その辺のそれぞれにセグメントの端点が含まれているので、この問題を一般化集合カバーのインスタンスとして定式化したいと思うでしょう。

関連する問題