А. Тимофеев

Обзор по преобразованиям контуров и планарных укладок графов (морфингу)

В докладе будут представлены несколько результатов в области преобразования наборов замкнутых контуров (многоугольников) и планарных укладок графов.

Задача поиска преобразования (морфинга) будет разобрана в нескольких различных постановках, от очень узких классов (ортогонально-выпуклых многоугольников и монотонного морфинга на них), где она оказывается NP-трудной, до очень общего случая допускающего набор непростых многоугольников с "дырками".

В качестве одного из наиболее мощных инструментов вычислительной геометрии в докладе будут представлены прямолинейные скелеты (straight skeletons).