0

N 次元の整数点のセットが与えられた場合、N 次元の直方体 (2 次元の場合は四角形) の最小のセットを見つけるにはどうすればよいですか? 1 つまたは複数の直方体/長方形。整数点とは、整数座標を持つ点を意味します。

たとえば、点 (1,0)、(2, 0)、および (3,1)、(4,1) が与えられた場合、長方形の最小のセットは (1,0-2,0),(3,1-4, 1)、下の図を参照してください。

2 .....
1 ...##
0 .##..
  01234

明らかに、ブルート フォース検索を行うこともできますが、それでも複雑性が高い場合でも、より効率的なアルゴリズムを探しています。

4

3 に答える 3

2

一般的なケースは NP 困難です:
http://www.computer.org/portal/web/csdl/doi/10.1109/SFCS.1988.21976

O(log N)で近似できるようです。「NP 最適化問題の概要」をオンラインで参照し、「MINIMUM RECTANGLE COVER」を検索してください。

また、特定のユースケースを効率的に解決できる場合もあります。

于 2009-12-13T19:11:24.850 に答える
1

ポイントが

4 .###.
3 ..#..
2 .###.
1 ..#..
0 .###.
  01234

次に、4 つの重なり合う長方形で覆うことができますが、重なり合わない 5 つの長方形が必要になります。

このアルゴリズムはどうですか：

各点について、その点を含む最大の長方形を見つけます。最大の長方形は、それ以上大きくすることはできず、ポイントをカバーするだけのものです。最大の長方形が 2 つある場合は、1 つを選択します。その最大の長方形を、重複を削除する何らかのデータ構造に格納します。すべてのポイントの反復処理が終了したら、長方形のセットがすべてのポイントをカバーする必要があります。

これが実際に長方形の最小セットであるかどうかはわかりませんが、そうだと思います。

上記の例では、縦に 1 つ、横に 2 つの 3 つの長方形が作成されることに注意してください。

于 2009-12-01T22:48:05.227 に答える
1

既存のポイントを見つけるには、多くの方法があります。

  1. すばやく検索できるように、ポイントをハッシュ マップに入れます。これは、ポイントを収集しようとした場合にポイントがどれだけの穴を残すかわからない一般的なケースでは、おそらく最良のアプローチです。最悪の場合、ポイントごとに 1 つの長方形が得られます。

  2. Z 座標が 1 つまたは少数の場合は、ポイントをビットマップ (1 ビット深度) に収集します。ビットマップのピクセルをオンにするだけです。

  3. 四角形のポイントを本当に収集する必要がある場合は、最初にそれらを (座標によって) 順序付けられたセットに配置する必要があります。このセットを何度も繰り返します。毎回、セットから最初のポイントを取ります。次に、すでに持っている点の左/右に隣接する点を探します。1 つある場合は、(水平) 行に結合します。より多くのポイントを獲得するにつれて、そのラインを伸ばします。

ポイントが残っていない場合は、線についても同じことを行い、長方形を成長させます。

于 2009-07-16T14:00:58.287 に答える