Решение задачи 14.
а) Обозначим вершины N-угольника x(0), ..., x(N-1) в порядке обхода по контуру. В дальнейшем будем считать, что если у нас в выкладках встречается вершина с индексом k, то это то же, что и вершина с номером k mod N (остаток от деления k на N).
Рассмотрим выпуклый L-угольник, вершинами которого являются L
последовательных вершин данного N-угольника, начиная с x(p) и до x(p+L-1) (в порядке обхода по контуру). У этого L-угольника будем считать, что отрезок (x(p),x(p+L-1)) - это его диагональ. Сумму диагоналей этой фигуры обозначим S(p,p+L-1).
Очевидно, что по условию задачи:
S(p,p)=0; S(p,p+1)=0 (у точки и отрезка нет диагоналей),
S(p,p+2)=d(p,p+2)
(тут d(p,p+2) - длина отрезка (x(p),x(p+2))).
Предположим, что мы знаем S(p,p+L-1) для всех p=0, ...,N-1 и L=1,...k.
Найдем S(p,p+k).
Мы знаем, что диагонали разбивают k+1 угольник на треугольники, и что (x(p),x(p+k)) - диагональ, т.е. одна из сторон какого-то треугольника. Итак, мы зафиксировали две вершины треугольника x(p) и x(p+k). Третьей вершиной может быть либо x(p+1), либо x(p+2),..., либо x(p+k-1). Если мы считаем, что третья вершина это x(i), то сумма диагоналей будет
d(p,p+k) + S(p,i) + S(i,k). (1)
Тут мы уже знаем S(p,i) и S(i,k) - они, по предположению, были вычислены на предыдущих шагах. d(p,p+k) - это расстояние между вершинами x(p) и x(p+k), его мы тоже можем вычислить.
Так как нас интересует минимальная сумма триангуляции (разбиения на треугольники), то мы ищем выражение (1) с минимальным значением
S(p,p+k)=d(p,p+k)+ min{S(p,i)+S(i,k)} (2) i
при i=p+1,p+2,...,k-1.
Находим S(p,p+k) для каждого p=0,...,N-1.
Минимум S(p,p+N-2) по p=0,...,N-1, и даст искомую триангуляцию (действительно, S(p,p+N-2) есть стоимость разбивки фигуры после проведения N-3 диагоналей).
б) Алгоритм остается тем же, за исключением того, что вместо формулы (2) надо использовать следующую:
S(p,p+k)={d(p,p+k),S(p,i),S(i,k)},
где S(p,p+k) - длина максимальной диагонали в фигуре с вершинами x(p), x(p+1), ...,x(p+k) (отрезок (x(p),x(p+k)) считается диагональю). Мы берем минимум по всем возможным разбивкам фигуры, а стоимость разбивки определяется как максимум из длины диагонали d(p,p+k) и длин максимальных диагоналей S(p,i) и S(i,k).
|
