Олимпиадная задача по комбинаторной геометрии: точки внутри n-угольник

  Оценка. Поскольку n-угольник можно разрезать диагоналями на  n – 2  треугольника и в каждом из них должно быть по точке, то необходимо отметить по крайней мере  n – 2  точки.

  Пример. Обозначим вершины n-угольника A₀, A₁, ..., A_n–1. Поставим k-ю точку B_k  (k = 1, 2, ..., n –2)  "вблизи" вершины A_k внутри угла A₀A_kA_n (точнее, в пересечении этого угла и треугольника A_k–1A_kA_k+1). Рассмотрим произвольный треугольник A_iA_kA_j  (i < k < j).  Этот треугольник содержит точку B_k, поскольку угол A_iA_kA_j содержит угол A₀A_kA_n, а диагональ A_k–1A_k+1 пересекает отрезки A_iA_k и A_kA_j.