Математическое моделирование на графах. Часть 1. Берцун В.Н. - 71 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

Глава 2. Плоские и планарные графы 71
Диаграмма Вороного является классическим математическим
объектом, что позволяет упростить решение большого класса задач
определения близости.
Задача построения зон близости требует нахождения всех точек
плоскости, для которых расстояние ρ до объектов множества {P
i
}
минимально. В случае, когда все объекты точечные, эта задача сво-
дится к построению диаграммы Вороного. Например, такие диа-
граммы могут использоваться не только для нахождения зон ско-
рейшего обслуживания (достижимости) из заданных базовых пунк-
тов, но и при решении краевых задач [51 – 55].
В археологии ячейки Дирихле используются для нанесения на
карту ареала применения орудий труда в древних культурах и для
изучения влияния соперничающих центров торговли. В экологии
возможности организма на выживание зависят от числа соседей, с
которыми он должен бороться за пищу и свет. Использование диа-
граммы Вороного, отражающей картину расселения животных и
распределения жизненно важных ресурсов, помогает исследовать
эффект перенаселенности. Совместное влияние электрических и
близкодействующих сил, для изучения которых строятся сложные
диаграммы Вороного, помогает определять структуру молекул.
Среди множества известных методов восстановления сеточных
функций особое место занимает интерполяция Сибсона [56], которая
основана на разбиении пространства по ячейкам Дирихле.
Пусть на множестве S узлов интерполяции P
i
, i = 1, …, n, известна
диаграмма Вороного. Если P
0
– точка интерполирования, то постро-
им диаграмму на множестве из n + 1 точки P
0
, P
i
, i = 1, …, n. Интер-
поляция Сибсона основана на вычислении линейной комбинации
0
11
.., 1 , / 0 ,
MM
mm m m m
mm
ff D
==
=α α= α=
β
≥
∑∑
(8)
где М – число соседей точки P
0
, α
m
– весовые коэффициенты, D –
площадь ячейки Дирихле для точки P
0
.
Коэффициенты β
m
есть площади, которые вырезаются из ячейки
Дирихле для точки P соответствующими ячейками Дирихле, при-
надлежащими соседям P
0
и построенными по множеству S.

Страницы