TOPICS
Search

Convex Polygon


ConvexPolygon

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 n vertices x_i for i=1, 2, ..., n, and define the edge vectors as

 v_i=x_(i+1)-x_i,
(1)

where x_(n+1) is understood to be equivalent to x_1. 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

 v_i^_|_·v_(i+1)
(2)

has the same sign for all i, where a^_|_·b 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 n-gons and the minimal number of points f(n) (in the general position) in which a convex n-gon can always be found. The answers for n=3, 4, 5, and 6 are 3, 5, 9, and 17. It is conjectured that f(n)=2^(n-2)+1, but only proven that

 2^(n-2)<=f(n)<=(2n-4; n-2),
(3)

where (n; k) is a binomial coefficient.


See also

Concave Polygon, Convex Hull, Convex Polyomino, Convex Polyhedron, Convex Polytope, 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

Convex Polygon

Cite this as:

Weisstein, Eric W. "Convex Polygon." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ConvexPolygon.html

Subject classifications