Boundary conforming Delaunay mesh generation

Изучается разбиение многогранной области на симплексы Делоне такое, что все граничные симплексы удовлетворяют обобщенному условию Габриэля. Разбиение Вороного этой же области является двойственным разбиению Делоне, и оказывается предпочтительным при использовании методов конечного объема на ячейках Вороного. Для произвольных двумерных многоугольных областей можно строить оптимальные по размерности сетки с оптимальной вычислительной сложностью. Для произвольных трехмерных многогранных областей эта задача остается нерешенной. Основной результат данной статьи заключается в том, что существует эффективный алгоритм построения сеток Делоне, сообразных границе, внутри трехмерных многогранных областей, если минимальный входящий угол между смежными гранями изнутри области ограничен снизу величиной $\arccos1/3\approx 70.53^\circ$. К тому же, можно получить заданное распределение размера тетраэдров сетки притом, что мера искажения формы тетраэдров ограничена сверху. Новые результаты получены посредством анализа классического метода сгущения сеток Делоне. Заметим, что полученная теоретическая гарантия по входному углу $(70.53^\circ)$ все еще слишком жесткая для многих практических случаев. Обсуждаются варианты алгоритма построения сеток, позволяющие ослабить требования к углу и улучшить качество сетки. Библ. 29. Фиг. 12. Табл. 1.