Convex Polygon (Polski)
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.,
niech prosty wielokąt ma wierzchołki dla , 2, …, I zdefiniować wektory krawędzi jako
(1) |
gdzie jest rozumiane jako równoważne . Wtedy wielokąt jest wypukły iff wszystkie obroty z jednego wektora krawędziowego do następnego mają ten sam sens., Dlatego prosty wielokąt jest wypukły iff
(2)
|
ma ten sam znak dla wszystkich , gdzie oznacza produkt perp Dot (Hill 1994). Jednak bardziej skuteczny test, który nie wymaga a priori wiedzy, że wielokąt jest prosty, jest znany (Moret and Shapiro 1991).,
problem happy end uwzględnia wypukłość-Gon i minimalną liczbę punktów (w pozycji ogólnej), w której zawsze można znaleźć wypukłość-gon. Odpowiedzi dla , 4, 5 i 6 to 3, 5, 9 i 17., It is conjectured that , but only proven that
(3)
|
where is a binomial coefficient.