Polygon covering とは

ポリゴンのカバーは、その組合がポリゴンに等しいプリミティブユニット(例えば、四角形)のセットである。ポリゴンカバー問題は、与えられたポリゴンに対して最小単位数のカバーリングを見つける問題である。これは、計算幾何学における重要な問題のクラスです。カバーされるポリゴンのタイプと、カバーで許容されるユニットのタイプに応じて、多くの異なるポリゴンカバー問題があります。多角形をカバーする問題の例は、直線状の多角形が与えられた場合、その多角形に等しい最小の正方形の集合を見つける。
いくつかのシナリオでは、ポリゴン全体をカバーする必要はなく、そのエッジ(ポリゴンエッジカバーリングと呼ばれます)またはその頂点(ポリゴン頂点カバーリングと呼ばれます)のみをカバーする必要があります。
覆いの問題では、対象のポリゴンとその合併が正確に等しい限り、被覆の単位は重なり合うことが許されます。これは、ユニットが分離していて、そのユニオンがターゲットポリゴンより小さくなければならないパッキングの問題と、ユニットが分離していて、それらのユニオンがターゲットと等しくなければならないポリゴンパーティションの問題ポリゴン。
ポリゴンカバー問題は、セットカバー問題の特別なケースです。一般に、最小の被覆を見つける問題はNP完全であるが、特別なクラスのポリゴンについては、最小のポリゴンカバーを多項式時間で見つけることができる。