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

Применение геометрических остовных сетей (посмотреть исходный код)

968 байт добавлено , 16 октября 2016

4430

правок

Версия от 00:13, 16 октября 2016 (просмотреть исходный код) Irina (обсуждение \| вклад) (→‎Основные результаты) ← Предыдущая правка		Версия от 23:47, 16 октября 2016 (просмотреть исходный код) Irina (обсуждение \| вклад) (→‎Применение) Следующая правка →
Строка 73:		Строка 73:

	== Применение ==		== Применение ==
			Как упоминалось ранее, вышеописанная структура данных может быть применена к некоторым другим задачам. Во-первых, это поиск ответов на запросы о расстоянии для планарной области с препятствиями в виде многоугольников. Более того, область к тому же должна быть t-округленной, что означает, что длина кратчайшего пути, огибающего препятствия, между любыми двумя точками входного множества, не более чем в t раз превышает евклидово расстояние между ними. Иными словами, граф видимости должен быть t-остовом входного множества точек.