Применение геометрических остовных сетей: различия между версиями

Пусть p и q – точки в пространстве <math>\mathbb{R}^d \;</math>. Будем использовать нотацию |pq| для обозначения евклидова расстояния между p и q, а нотацию <math>\delta_G (p q) \;</math> – для обозначения евклидовой длины кратчайшего пути между p и q в геометрической сети G. Пусть имеется константа t > 1. Граф G с множеством вершин S является t-остовом для S, если <math>\delta_G (p q) \le t |p q| \;</math>  для любых двух точек p и q из S. t-остовная сеть имеет [[протяженность]] (или растяжение) t. <math>(1 + \varepsilon) \;</math>-аппроксимацией кратчайшего пути между p и q является любой путь в графе G между p и q, имеющий длину <math>\Delta \;</math>, где <math>\delta_G (p q) \le \Delta \le (1 + \varepsilon)\delta_G (p q) \;</math> . Исчерпывающий обзор геометрических остовов можно найти в работе Нарасимхана и Смида [13].