Триангуляция плоских областей, заданных системой неравенств

Аннотация

В работе представлен метод построения триангуляции плоской, в общем случае многосвязной, области, которая задается системой неравенств. Основная идея данного подхода заключается в следующем. На первом шаге осуществляется построение стандартной триангуляции по прямоугольной сетке некоторого многоугольника, лежащего в заданной области. На втором шаге крайние узлы полученной триангуляции методом градиентного спуска сдвигаются на границу области. Доказывается, что синусы углов треугольников такой триангуляции не стремятся к нулю (треугольники не вырождаются) при стремлении к нулю их диаметров, если заданная область имеет гладкую границу.