|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ЦЭМИ РАН |
||
Метод латентных ребер для слияния перекрывающихся триангуляций Делонедипломная работа (Магистр)
- Научный руководитель: Местецкий Л.М.
- Автор: Готман М.Л.
- Тип: Магистр
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Год защиты: 2017
- Аннотация: В работе рассматривается задача слияния двух триангуляций Делоне (ТД), у которых множества их сайтов не пересекаются, а выпуклые оболочки имеют непустое пересечение. Такие триангуляции названы в работе перекрывающимися. Эта задача является одной из классических в вычислительной геометрии. Известны эффективные алгоритмы её решения, основанные на построении евклидовых минимальных остовных деревьев (ЕМОД) двух исходных триангуляций. В работе предпринята попытка решения задачи без использования ЕМОД. Мотивацией для этого исследования служит тот факт, что эффективные алгоритмы построения ЕМОД на основе триангуляции Делоне весьма сложны для реализации. В диссертации предложен более простой алгоритм сшивания ТД. Упрощение состоит в том, что вместо ребер ЕМОД предлагается использовать ребра ТД другого типа, которые в диссертации названы латентными. Сформулированы правила поиска таких ребер и разработан алгоритм сшивки двух триангуляций с использованием этих ребер. Корректность полученного алгоритма обоснована теоретически и проверена в вычислительных экспериментах.
- Добавил в систему: Местецкий Леонид Моисеевич