Convex Polygon (Italiano)
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.,
Lascia che un poligono semplice abbia
vertici
per
, 2, …, 
e definire il bordo vettori
 |
(1)
|
dove 
è da intendersi equivalente a 
. Quindi il poligono è convesso se tutti i giri da un vettore di bordo all’altro hanno lo stesso senso., Quindi, un semplice poligono è convesso iff
 |
(2)
|
ha lo stesso segno per tutti 
, dove 
indica il perp dot product (Hill, 1994). Tuttavia, un test più efficiente che non richiede a priori la conoscenza che il poligono è semplice è noto (Moret e Shapiro 1991).,
Il problema happy end considera convesso
-gons e il numero minimo di punti
(nella posizione generale) in cui è sempre possibile trovare un convesso
-gon. Le risposte per
, 4, 5 e 6 sono 3, 5, 9 e 17., It is conjectured that 
, but only proven that
 |
(3)
|
where 
is a binomial coefficient.