Вычислительная геометрия

Общая информация
ЛекторК. В. Вяткина
Семестрвесна 2014
Дата начала16.02.2014
Количество пар12
Язык курсарусский
Вопросы к экзамену
Аннотация

В рамках данного курса будут обсуждаться эффективные алгоритмы и структуры данных для решения геометрических задач и возможности их применения на практике. К основным его темам относятся выпуклые оболочки, диаграмма Вороного и триангуляция Делоне, а также задачи пересечения геометрических объектов и регионального поиска.

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

  1. M. de Berg, O. Cheong, M. van Kreveld, M.Overmars, "Computational Geometry: Algorithms and Applications", Third Edition, Springer-Verlag, 2008.
  2. J. O'Rourke, "Computational Geometry in C", Second Edition, Campbridge University Press, 1998.
  3. J.-D. Boissonnat, M. Yvinec, "Géométrie Algorithmique", Ediscience international, Paris, 1995. (Перевод на англ.: J.-D. Boissonnat, M. Yvinec, "Algorithmic geometry", Cambridge University Press, UK, 1998.)
  4. Ф. Препарата, М. Шеймос, "Вычислительная геометрия: Введение", М., Мир, 1989. (Перевод с англ.: F. Preparata, M. Shamos, "Computational Geometry: An Introduction", Springer-Verlag, 1985.)
  5. S. L. Devadoss and J. O’Rourke, "Discrete and Computational Geometry", Princeton University Press, 2011.
  6. D. Mount, Lecture notes: CMSC 754 "Computational Geometry", Dept. of Computer Science, University of Maryland, USA, Fall 2002.

Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

1. Введение
(16.02.2014 - 11:15 - 12:50)

Задачи вычислительной геометрии и оценка сложности алгоритмов их решения. Проверка принадлежности точки простому, выпуклому, звездному многоугольнику. Выпуклая оболочка множества точек на плоскости и наивный алгоритм ее построения. https://www.youtube.com/watch?v=_fwJA2_hXt4
2. Выпуклая оболочка
(02.03.2014 - 11:15 - 12:50)

Эффективные алгоритмы построения выпуклой оболочки множества точек на плоскости. https://www.youtube.com/watch?v=OxEAU2DFpCk
3. Выпуклая оболочка (окончание). Пересечение отрезков.
(09.03.2014 - 11:15 - 12:50)

Алгоритм Чена для построения выпуклой оболочки множества точек на плоскости. Задача пересечения отрезков: наивный алгоритм; нижняя оценка сложности; алгоритм, основанный на методе плоского заметания. http://www.youtube.com/embed/KXP59HTfeLg
4. Пересечение геометрических объектов
(16.03.2014 - 11:15 - 12:50)

Оценка сложности алгоритма пересечения отрезков, основанного на методе плоского заметания. Наложение плоских планарных подразбиений. Алгоритмы пересечения выпуклых многоугольников. Пересечение простых многоугольников. http://www.youtube.com/watch?v=oUXVA5k17To
5. Пересечение полуплоскостей. Триангуляция многоугольника
(16.03.2014 - 13:00 - 14:35)

Нахождение пересечения полуплоскостей. Триангуляция простого многоугольника: определение и свойства. Базовые алгоритмы триангуляции простого многоугольника. http://www.youtube.com/watch?v=rPRdolyL760
6. Триангуляция многоугольника (окончание)
(23.03.2014 - 11:15 - 12:50)

Алгоритм триангуляции монотонного многоугольника. Метод разбиения простого многоугольника на монотонные. http://www.youtube.com/watch?v=FnFHinXrjvE
7. Локализация точки на планарном подразбиении
(23.03.2014 - 13:00 - 14:35)

Постановка задачи. Детерминированные алгоритмы: метод полос, метод детализации триангуляции Киркпатрика. http://www.youtube.com/watch?v=b_-J9ZrH-CQ
8. Локализация точки на планарном подразбиении (окончание)
(06.04.2014 - 11:15 - 12:50)

Вероятностный алгоритм: трапецоидальные карты, их свойства и построение. http://www.youtube.com/watch?v=B_ivxdEK8eQ
9. Диаграмма Вороного
(13.04.2014 - 11:15 - 12:50)

Диаграмма Вороного для множества точек на плоскости: определение и основные свойства. http://www.youtube.com/watch?v=-IoB_Iex8b8
10. Построение диаграммы Вороного
(13.04.2014 - 13:00 - 14:35)

Алгоритм построения диаграммы Вороного, основанный на методе плоского заметания. http://www.youtube.com/watch?v=ooqKwgvDi98
11. Триангуляция Делоне
(20.04.2014 - 11:15 - 12:50)

Определение и свойства триангуляций множества точек на плоскости. Легальные (legal) триангуляции: определение и построение. Граф Делоне и его свойства. Триангуляция Делоне. http://www.youtube.com/watch?v=mz_hz3nrze8
12. Конфигурации прямых и двойственность в вычислительной геометрии
(27.04.2014 - 11:15 - 12:50)

Задача о вычислении расхождения (discrepancy). Двойственность точек и прямых. Конфигурации (arrangements) прямых на плоскости: определение, сложность, инкрементный алгоритм построения. Понятие зоны прямой в конфигурации; теорема о зоне (Zone Theorem). Оценка сложности инкрементного алгоритма построения конфигурации. Понятие уровня (level) точки в конфигурации прямых. Вычисление уровней вершин конфигурации и их связь с величиной расхождения. http://www.youtube.com/watch?v=MdcKlmjp_jU
Ваша оценка: Пусто Средняя: 5 (4 голосов)
Share |
Кира Вяткина
Кира Вяткина и студенты