Механизм колабса ребра.

Цель: выбор ребра, от которого можно избавмться, но это избавление должно принести наименьшую ошибку. Рассмотрим пример:

 

Во-первых, нам нужно найти квадрики всех вершин, а затем и рёбер.

Для примера возьмём ребро {1-2}:

 

Квадрик этого ребра:

Во-вторых, для каждого ребра считаем критерий, выбирая лучший переброс:

 

Критерий для ребра {1-2}:

,

так как

Затем выбираем ребро с наименьшим значением , которое и будет удалено.

Замыкание будет зависеть от следующего критерия:

- удаляется

- удаляется

Результат:

Мы выбрали такое перемещение, которое приносит наименьшую ошибку.

 

Примечание:

При перебросе квадрики вершин изменяются, следовательно, их нужно пересчи-

тать, а значит стоимость рёбер так же поменяется.

 

С помощью квадрика мы можем порождать новую вершину:

 

Допустим, мы хотим перекинуть все связи в

точку О. Координаты этой точки нам не изве-

стны, но мы можем их найти следующим об-

разом:

Получается, что

Минимальный критерий для точки :

Т.е. квадрик несёт в себе информацию об оптимальной точке, в которую можно

свести все связи.

 

Существует механизм работающий на квадриках и записи информации преды-

дущего шага. Т.е., допустим, мы стягиваем все связи, принадлежащие точкам 1

и 2, в точку О. При этом мы можем запомнить эту информацию и при обратном

щаге уже будем знать как разлажить точку О(т.е. на точку 1 и точку 2).