Computational Geometry

2020/2021

Academic Year

RUS

Instruction in Russian

4

ECTS credits

Delivered at:

Department of Informatics

Course type:

Elective course

When:

4 year, 1, 2 module

Instructor

Ковалев Антон Сергеевич

Программа дисциплины

Аннотация

Является дисциплиной по выбору. Студенты получат представление об основных алгоритмах вычислительной геометрии. Научатся создавать эффективные программы для решения характерных задач в этой области В результате освоения дисциплины студент должен:  знать алгоритмы вычислительной геометрии;  уметь создавать эффективные по времени и памяти программы для решения задач данной области;  владеть математическим аппаратом и инструментальными средствами, используемым в вычислительной геометрии.

Цель освоения дисциплины

• Целями освоения дисциплины «Вычислительная геометрия» являются формирование у студентов теоретических знаний и практических навыков по основам вычислительной геометрии. Студенты получат представление об основных алгоритмах вычислительной геометрии. Научатся создавать эффективные программы для решения характерных задач в этой области.

Планируемые результаты обучения

• Владеет понятиями: принадлежность точки многоугольнику; выпуклые оболочки; пересечение отрезков и многоугольников.
• Владеет понятиями: триангуляция простого многоугольника. Владеет понятиями: разбиение многоугольника на монотонные многоугольники; триангуляция монотонного многоугольника. Знает: метод детализации триангуляции Киркпатрика.
• Владеет понятием: трапецоидальная карта (основные свойства, построение) Знает диаграмму Вороного: основные свойства, построение.
• Владеет понятиями: триангуляция множества точек на плоскости; триангуляция Делоне; планирование пути.

Содержание учебной дисциплины

• Принадлежность точки многоугольнику, пересечение отрезков
• Триангуляция простого многоугольника. Разбиение на монотонные многоугольники.
• Трапецоидальная карта и диаграмма Вороного
• Триангуляция множества точек, планирование пути

Элементы контроля

• Домашнее задание 1
• Домашнее задание 2
• Домашнее задание 3
• Домашнее задание 4
• Устный экзамен

Промежуточная аттестация

• Промежуточная аттестация (2 модуль)
  0.125 * Домашнее задание 1 + 0.125 * Домашнее задание 2 + 0.125 * Домашнее задание 3 + 0.125 * Домашнее задание 4 + 0.5 * Устный экзамен

Список литературы

Рекомендуемая основная литература

• Boissonnat, J.-D., & Teillaud, M. (2006). Effective Computational Geometry for Curves and Surfaces. Berlin: Springer. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=176637

Рекомендуемая дополнительная литература

• Computational geometry : algorithms and applications. (2008). Springer. https://doi.org/10.1007/978-3-540-77974-2