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.
See also
Concave Polygon, Convex Hull, Convex Polyomino, Convex Polyhedron, Happy End Problem, Lattice Polygon, Polygon
Explore with Wolfram|Alpha
References
Hill, F. S. Jr. "The Pleasures of 'Perp Dot' Products." Ch. II.5 in Graphics Gems IV (Ed. P. S. Heckbert). San Diego: Academic Press, pp. 138-148, 1994.Moret, B. and Shapiro, H. Algorithms from P to NP. Reading, MA: Benjamin Cummings, 1991.
Referenced on Wolfram|Alpha
Cite this as:
Weisstein, Eric W. "Convex Polygon." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ConvexPolygon.html