Определение триангуляции и задачи ее построения

  В литературе часто встречается следующее определение триангу­ляции: триангуляцией называется планарный граф, все внутренние области которого являются треугольниками. Данное определение бу­дет уточнено в п. 1.4.3.
    Вспомним: планарный граф – это граф, который может быть изображен на плоскости без пересечения ребер.
    Следует обратить внимание на тот факт, что триангуляция может быть как выпуклой, так и невыпуклой, причем выпуклой триангуляцией называется такая триангуляция, для которой минимальный многоугольник, охватывающий все треугольники, будет выпуклым. Триангуляция, не являющаяся выпуклой, называется невыпуклой.
   Задачей построения триангуляции по заданному набору двумер­ных точек (заданных своими декартовыми координатами) называет­ся задача соединения заданных точек непересекающимися отрезками так, чтобы образовалась триангуляция.

.