Интуитивное определение триангуляции
Так как любую область можно разбить на треугольники, попытайтесь соединить заданные на плоскости точки (рис 1, а) непересекающимися отрезками таким образом, чтобы каждая область внутри выпуклой оболочки этого множества (рис. 1, б) являлась треугольником.
Вспомним: выпуклой оболочкой множества точек S называется наименьшее выпуклое множество, содержащее S (см. [5]).
![]()
Рис. 1. Множество точек - а; б - выпуклая оболочка этих точек
Сравните свой вариант с нижеприведенными (рис. 2).
![]()
Рис. 2. Некоторые варианты соединения точек непересекающимися отрезками таким образом, чтобы каждая область внутри выпуклой оболочки являлась треугольником
Совпал ли ваш вариант с каким-либо?
Если даже и нет, в этом нет ничего страшного, так как вариантов построения триангуляции существует множество. Доказано, что планарный граф с и вершинами имеет не более 3 и - 6 ребер.
Каждое из таких разбиений (рис. 2) называют триангуляцией (от лат. triangulum – треугольник).