4551
правка
Геометрическая протяженность геометрических сетей: различия между версиями
Перейти к навигации
Перейти к поиску
м
Геометрическая протяженность геометрических сетей (посмотреть исходный код)
Версия от 13:54, 29 января 2018
, 29 января 2018→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 18: | Строка 18: | ||
Это определение отличается от понятия коэффициента растяжения, использовавшегося в контексте остовных деревьев; подробнее об этом – в монографиях Эпштейна [6] или Нарасимхана и Смида [11]. В последней рассматриваются только пути между вершинами <math>p, q \in V \;</math>, тогда как понятие геометрической протяженности включает также все точки на ребрах. | Это определение отличается от понятия коэффициента растяжения, использовавшегося в контексте остовных деревьев; подробнее об этом – в монографиях Эпштейна [6] или Нарасимхана и Смида [11]. В последней рассматриваются только пути между вершинами <math>p, q \in V \;</math>, тогда как понятие геометрической протяженности включает также все точки на ребрах. Таким образом, коэффициент растяжения треугольника T равен 1, однако его геометрическая протяженность задается формулой <math>\delta(T) = \sqrt{2 / (1 - cos \; \alpha)} \ge 2</math>, где <math>\alpha \le 60^\circ \;</math> - самый острый угол T. | ||
Пусть дано конечное множество S точек на плоскости. Требуется найти конечную геометрическую сеть, содержащую S, геометрическая протяженность которой насколько возможно мала. Значение | Пусть дано конечное множество S точек на плоскости. Требуется найти конечную геометрическую сеть, содержащую S, геометрическая протяженность которой насколько возможно мала. Значение | ||
<math>\Delta(S) := inf \{ \delta(G); G \;</math> – конечная плоская геометрическая сеть, содержащая S} | <math>\Delta(S) := inf \{ \delta(G); G \;</math> – конечная плоская геометрическая сеть, содержащая <math>S \} \;</math> | ||
называется ''геометрической протяженностью множества точек'' S. Задача заключается в вычислении или ограничении <math>\Delta(S) \;</math> для данного множества S. | называется ''геометрической протяженностью множества точек'' S. Задача заключается в вычислении или ограничении <math>\Delta(S) \;</math> для данного множества S. | ||