Sa sdasa sad

  • 10 марта 2011 г.
  • 951 Слова
ЭФФЕКТИВНЫЙ АЛГОРИТМ ПОСТРОЕНИЯ ДИАГРАММ ВОРОНОГО
С.Н. Карабцев, С.В. Стуколов
Кемеровский государственный университет
skarab@kemsu.ru, serg@kemsu.ru

Для применения того или иногочисленного метода первым делом необходимо произвести дискретизацию расчетной области на более мелкие подобласти. Например, в методе конечных элементов разбиение производится треугольными элементами при помощитриангуляции Делоне. Данный процесс очень сложен, и не гарантирует, что все элементы будут обладать заданным качеством (например, равенство углов треугольника). Но от качества триангуляции зависит точность аппроксимациифункции на элементе.
По имеющейся триангуляции Делоне можно построить двойственную ей структуру, которая будет лишена большинства недостатков, - диаграмму Вороного. Данное разбиение отличается тем,что все его элементы выпуклые, и нет многоугольников, имеющих острые углы. Для любого центра системы [pic] можно указать область пространства, все точки которой ближе к данному центру, чем к любомудругому центру системы. Такая область называется многогранником Вороного или областью Вороного. К многограннику Вороного обычно относят и его поверхность. В трехмерном пространстве область Вороного любогоцентра [pic] системы [pic] есть выпуклый многогранник, в двумерном — выпуклый многоугольник. Математически многоугольники Вороного [pic] определяются следующим образом:
[pic] (1)
Всовременном бессеточном методе конечных элементов MFEM применяется интерполяция Лапласа [1, 2]. Построение аппроксимации опирается на фундаментальное свойство для произвольно заданных [pic] точек множества [pic] наплоскости. Для любого узла из [pic] на плоскости существует множество натуральных соседей [pic]. Понятие натуральных соседей тесно связано с разбиением области ячейками Вороного. Для непустой ячейкиВороного [pic] натуральные соседи для [pic] - вершины треугольников Делоне, инцидентных к [pic].
Двумерный многогранник Вороного показан на рисунке 1....
tracking img