Convex Polygon (日本語)

0 Comments
Geometry > PlaneGeometry > Polygons >

A planar polygon is convex if it contains all the line segments connecting any pair of its points. Thus, for example, a regular pentagon is convex (left figure), while an indented pentagon is not (right figure). A planar polygon that is not convex is said to be a concave polygon.,

単純なポリゴンに頂点,2,を持たせます。..,としてエッジベクトルを定義します

(1)

ここで、と同等であると理解されます。 次に、ある辺ベクトルから次の辺ベクトルへのすべてのターンが同じ意味を持つ場合、多角形は凸です。, したがって、単純なポリゴンは凸であるiff

(2)

すべてのここで、はperpドット積を表します(hill1994)。 しかし、多角形が単純であるという先験的な知識を必要としない、より効率的なテストが知られている(Moret and Shapiro1991)。,

ハッピーエンド問題は、凸-gonsと最小点数-gonを常に見つけることができる(一般的な位置において)。 、4、5、および6の答えは3、5、9、および17です。, It is conjectured that , but only proven that

(3)

where is a binomial coefficient.


コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です