Convex Polygon

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.

Let a simple polygon have vertices for , 2, ..., , and define the edge vectors as

(1)

where is understood to be equivalent to . Then the polygon is convex iff all turns from one edge vector to the next have the same sense. Therefore, a simple polygon is convex iff

(2)

has the same sign for all , where denotes the perp dot product (Hill 1994). However, a more efficient test that doesn't require a priori knowledge that the polygon is simple is known (Moret and Shapiro 1991).

The happy end problem considers convex -gons and the minimal number of points (in the general position) in which a convex -gon can always be found. The answers for , 4, 5, and 6 are 3, 5, 9, and 17. It is conjectured that , but only proven that

(3)

where is a binomial coefficient.

Wolfram Web Resources