Триангуляция с минимальным весом

Материал из WEGA
Версия от 14:54, 25 сентября 2016; Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Триангуляция минимальной длины == Постановка задачи == Пуст…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

Ключевые слова и синонимы

Триангуляция минимальной длины

Постановка задачи

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

Основные результаты