Оптимальная триангуляция многоугольника

Несмотря на свою геометрическую формулировку, эта задача очень близка к задаче о перемножении матриц.

Многоугольник (polygon)—это замкнутая кривая на плоскости, составленная из отрезков, называемых сторонами (sides) многоугольника. Точка, в которой сходятся две соседние стороны, называется вершиной (vertex). Несамопересекающийся многоугольник (только такие мы и будем, как правило, рассматривать) называется простым (simple). Множество точек плоскости, лежащих внутри простого многоугольника, называется внутренностью (interior) многоугольника, объединение его сторон называется его границей (boundary), а множество всех остальных точек плоскости называется его внешностью (exterior). Простой многоугольник называется выпуклым (convex), если для любых двух точек, лежащих внутри или на границе многоугольника, соединяющий их отрезок целиком лежит внутри или на границе многоугольника.

Выпуклый многоугольник можно задать, перечислив его вершины против часовой стрелки: многоугольник P=(v₀,v₁,...,v_n-1) имеет п сторон . Здесь v_n— то же самое, что v₀ (удобно нумеровать вершины n- угольника вычетами по модулю n).

Если v_i и v_j — две вершины, не являющиеся соседними, отрезок ; называется диагональю (chord) многоугольника. Диагональ разбивает многоугольник на два: и . Триангуляция (triangulation) многоугольника- это набор диагоналей, разрезающих многоугольник на треугольники; сторонами этих треугольников являются стороны исходного

Рис. 4. Две триангуляции выпуклого семиугольника. Каждая делит семиугольник на 7-2=5 треугольников с помощью 7-3=4 диагоналей.

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

Во всех триангуляциях n-угольника одно и то же число треугольников (сумма всех углов многоугольника равна произведению 180° и числа треугольников в триангуляции), а именно п- 2. При этом используются n- 3 диагональ (проводя диагональ, мы увеличиваем число частей на 1).

Задача об оптимальной триангуляции (optimal triangulation problem) cocтоит в следующем. Дан выпуклый многоугольник Р= (v₀,v₁,...,v_n-1) и весовая функция w, определённая на множестве треугольников с вершинами в вершинах Р. Требуется найти триангуляцию, для которой сумма весов треугольников будет наименьшей.

Естественный пример весовой функции—функция

где | v_iv_j | обозначает евклидово расстояние между v_i и v_j. Мы построим алгоритм решения этой задачи, который применим для любой весовой функции.

Дата добавления: 2015-12-08