Триангуляция с минимальным весом: различия между версиями

Пусть дан набор S из n точек на евклидовой плоскости. [[Триангуляция]] T набора S представляет собой максимальное множество непересекающихся прямолинейных сегментов, конечные точки которых принадлежат S. Вес T определяется как полная евклидова длина всех ребер T. Триангуляция S, обеспечивающая минимальный вес, называется триангуляцией с минимальным весом и обозначается MWT (minimum weight triangulation).