Интуитивное определение триангуляции

    Так как любую область можно разбить на треугольники, попытай­тесь соединить заданные на плоскости точки (рис 1, а) непересекаю­щимися отрезками таким образом, чтобы каждая область внутри вы­пуклой оболочки этого множества (рис. 1, б) являлась треугольником.
    Вспомним: выпуклой оболочкой множества точек S называется наименьшее выпуклое множество, содержащее S (см. [5]).

 

Рис. 1. Множество точек - а; б - выпуклая оболочка этих точек

 

      Сравните свой вариант с нижеприведенными (рис. 2).


 

Рис. 2. Некоторые варианты соединения точек непересекающимися отрезками таким образом, чтобы каждая область внутри выпуклой оболочки являлась треугольником

     Совпал ли ваш вариант с каким-либо?
    Если даже и нет, в этом нет ничего страшного, так как вариантов построения триангуляции существует множество. Доказано, что планарный граф с и вершинами имеет не более 3 и - 6 ребер.
     Каждое из таких разбиений (рис. 2) называют триангуляцией (от лат. triangulum – треугольник).