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

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

68 В.Н. Берцун. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НА ГРАФАХ. Часть 1
Такая форма записи удобна для интерполяции внутри треугольника
для нескольких массивов сеточных функций.
Локальный сплайн вида (6) дает возможность восстановить зна-
чение функции f
(x, y) в любой точке треугольных граней, содержа-
щихся в выпуклом многоугольнике M
k
.
Диаграмма Вороного [40, 46, 49] конечного множества S точек на
плоскости – это такое разбиение плоскости, при котором каждая об-
ласть этого разбиения образует множество точек, более близких к
одному из элементов множества S, чем к любому другому элементу
этого множества. Область разбиения V(i), содержащая элемент P
i
∈S,
называется многоугольником Вороного. Такие многоугольники
впервые были рассмотрены русским математиком Вороным (1868 –
1908), использовавшим их в работе по квадратичным формам. Ино-
гда V(i) также называют ячейками Дирихле или многоугольниками
Тиссена.
Будем считать, что на множестве S можно построить единствен-
ную триангуляцию Делоне с остроугольными треугольниками, тогда
центры описанных окружностей лежат внутри треугольников. Пусть
P
i
∈S является внутренней точкой выпуклого многогранника, по-
строенного на множестве точек S. Пусть k треугольников триангуля-
ции Делоне имеют общую вершину P
i
. Соединив центры описанных
окружностей смежных треугольников этой группы, получим замк-
нутый выпуклый многоугольник, содержащий k вершин. Он и явля-
ется ячейкой V(i) диаграммы Вороного, имеющей центр в точке Р
i
,
как это изображено на рис. 2.25 для k = 5.
Из построения следует, что
каждое ребро диаграммы Воро-
ного является отрезком прямой,
перпендикулярной ребру триан-
гуляции, соединяющему некото-
рую пару точек множества S, и
делящей этот отрезок (ребро)
пополам. Таким образом, каждое
ребро триангуляции принадле-
жит в точности двум много-
P
i
Vi
()
Рис. 2.25

Страницы