Математическая модель оптимальной триангуляции

Формализована постановка задачи синтеза оптимальной плоской выпуклой триангуляции. Данная задача относится к вопросам приложений информатики и весьма актуальна в таких областях, как компьютерная графика и геоинформационные системы. Математическая модель представлена в трех вариантах: экстремальная задача с бесконечным числом ограничений, минимаксная задача со связанными переменными и экстремальная задача с дополнительным ограничением на пересечения отрезков триангуляции, но конечным числом всех ограничений. Путем введения идемпотентных ограничений на булевы переменные исходная целочисленная задача погружена в общую задачу математического программирования на континуальном множестве решений. Произведен сравнительный анализ решений, получаемых жадным алгоритмом на основе представленной математической модели и алгоритмом триангуляции Делоне.