Программа дисциплины вычислительная геометрия Цели изучения дисциплины



Дата14.05.2019
өлшемі48 Kb.
#149106
түріРабочая программа


РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ




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




Цели изучения дисциплины
При изучении дисциплины должны быть получены знания о способах обработки и представлениях геометрических и стереометрических данных в компьютере, умение оценить эффективность алгоритма обработки для конкретной задачи и навыки написания компьютерных программ обработки данных указанных типов.
Желательно знание разделов дисциплин «Дискретная математика», «Линейная алгебра», «Теория алгоритмов».


Содержание разделов дисциплины

Введение. О чем наука. Сложности: o, O, theta, omega. Представление базовых данных - точка, прямая, отрезок, треугольник. Направление обхода, площадь треугольника. Многоугольник, граница.

Многоугольники. Принадлежность точки многоугольнику (прямая и угол). Выпуклость, выпуклый многоугольник, выпуклая оболочка. Принадлежность точки выпуклому многоугольнику (по углу, по направлению). Звездный многоугольник, ядро.

Монотонный многоугольник.



Выпуклая оболочка множества точек в R2. Задача о выпуклой оболочке множества точек. Алгоритмы n4, n3. Оценка нижней границы сложности. Алгоритмы Jarvis, Graham, оценки сложности. Алгоритм Akl-Toussaint, оценка сложности. Алгоритм QHULL, оценка сложности. Опорные прямые, алгоритм DC1. Слияние выпуклых оболочек - вариации на тему обхода Graham, Akl - Toussaint. Алгоритмы DC2, DC3 и оценки сложности. Инкрементальный алгоритм и модификации, оценки сложности.

Выпуклая оболочка многоугольника. Тривиальный алгоритм, оценка сложности снизу. Свойство параллельных опорных прямых. Алгоритм Шеймоса, корректность. Приближенный алгоритм построения выпуклой оболочки, корректность, использование целой части числа, оценка погрешности.

Многогранники. Определение. Правильные многогранники (платоновы тела). Genus многогранника. Теорема Эйлера. Линейная сложность многогранника. Представление многогранника, РСДС.

Выпуклая оболочка множества точек в R3. Задача о выпуклой оболочке множества точек в R3. Оценка снизу. Обобщения на R3 алгоритмов Jarvis, DC, оценки сложности. Инкрементальный алгоритм, сложность.

Триангуляция. Постановка задачи. Выпуклые и вогнутые вершины. Лемма о существовании диагонали. Существование триангуляции. Сложность триангуляции.

Тривиальный алгоритм триангуляции. Двойственный граф триангуляции. Теорема Мейстера. Алгоритм Otectomy, сложность. 3-раскрашиваемость графа триангуляции. Задача Art-Gallery. Замечания о триангуляции множества точек.



Разбиение на выпуклые многоугольники. Постановки задачи: два критерия оптимальности (время или число частей), диагонали или произвольные отрезки. Оценка числа выпуклых частей для случая произвольных отрезков. Существенная диагональ. Оценка числа существенных диагоналей при невыпуклой вершине. Алгоритм Hertel-Mehlhorn, сложность и оценка эффективности.

Диаметр множества. Задача о поиске диаметра выпуклого многоугольника. Лемма о порядке экстремальных точек. Лемма о месте для наиболее удаленной точки. Алгоритм обхода, корректность, сложность. Задача о поиске диаметра множества точек. Сведение к ней задачи пересечения двух множеств, нижняя оценка. Алгоритм поиска диаметра, оптимальность.

Описанные прямоугольники. Задача о поиске описанного прямоугольника минимальной площади/периметра для выпуклого многоугольника. Постановка. Сужение области поиска решения, теорема Freeman-Shapiro. Тривиальный алгоритм, ускорение до O(nlogn). Вращающиеся калиперы, корректность. Ускорение тривиального алгоритма до O(n). Приближенный алгоритм построения описанного прямоугольника. Тривиальный вариант, ускорение, оценка точности.

Ограничивающие объемы. Применение. Шар, AABB, OBB. Приближенный алгоритм построения описанного OBB. Совпадение с гранью или с ребром.

Вероятностные алгоритмы. Постановка задач: сортировка и поиск. QSORT - рандомайзные подходы: conflict list и рекурсивный. Оценка сложности в среднем. Оценка глубины дерева в среднем. Динамизация, вращения. Линейное программирование. Рандомайзный подход. Оценка сложности в среднем.

Ограничивающий круг минимального радиуса. Постановка. Сужение области поиска решения. Единственность решения, радиус описанного круга для подмножества. Тривиальный алгоритм, сложность. Алгоритм MINDISC. Равномерная оценка сложности. Оценка сложности в среднем.

Монотонные многоугольники. Постановка задачи разбиения многоугольника на монотонные. Классификация вершин. Признак монотонности. Алгоритм разбиения, корректность, сложность. Триангуляция за O(nlogn). Схема. Триангуляция монотонного многоугольника: алгоритм, корректность, сложность. Обобщение на планарный граф.

Множество полуплоскостей. Задача о пересечении выпуклых многоугольников, сложность результата. Алгоритм Сазерленда-Коэна, сложность, ускорение до O(nlogn).

Алгоритм Шеймоса-Хоуи: две интерпретации, заметание по углу, оценка сложности. Пересечение множества полуплоскостей, оценка сложности. Следствие о звездных многоугольниках, алгоритм пересечения, сложность.



Второй семестр

Повторение. Представление геометрических данных в - R2 и R3. Планарное подразбиение плоскости, РСДС.

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

Пересечение множества отрезков. Постановка задачи. Тривиальный алгоритм. Оценка сложности снизу. Динамический алгоритм, корректность, сложность. Пересечение ППЛГ. Постановка задачи. Алгоритм, оценки сложности.

Ядро многоугольника. Постановка задачи. Сведение к задаче о полуплоскостях. Оценка сложности. Рандомайзный подход. Корректность, сложность.

Нахождение ближайших точек. Постановка задачи. Оценка сложности снизу. Связи с задачами сортировки, триангуляции, поиском ближайшей пары, поиском совпадающих элементов. Алгоритм, сложность.

Диаграмма Вороного. Определение. Свойства. Алгоритм построения. Корректность, сложность. Триангуляция Делоне. Свойства. Алгоритм построения. Применения к задачам: поиск наибольшей пустой окружности, построение минимального остовного дерева.

Планирование пути. Постановка задачи. Метод графа видимости. Алгоритм построения, сложность. Метод карты дорог. Алгоритм построения, сложность. Метод потенциалов, связь с диаграммой Вороного.

Упорядочивание линий. Постановка задачи. Связь с компьютерной графикой. Минимизация расхождения. Построение РСДС. Двойственное преобразование. Алгоритм упорядочивания. Корректность, сложность. Зонная теорема, следствия.
Лабораторный практикум
Предусматривается выполнение 4 лабораторных работ из списка:

  1. Принадлежность точки многоугольнику;

  2. Выпуклая оболочка за n4 и упорядочивание вершин;

  3. Выпуклая оболочка за n3 и упорядочивание вершин;

  4. Выпуклая оболочка - алгоритм Jarvis;

  5. Выпуклая оболочка - алгоритм Graham;

  6. Выпуклая оболочка - алгоритм Akl – Toussaint;

  7. Выпуклая оболочка - алгоритм QHULL;

  8. Выпуклая оболочка - инкрементальный алгоритм;

  9. Приближенный алгоритм построения выпуклой оболочки;

  10. Триангуляция за n3;

  11. Триангуляция - алгоритм Otectomy;

  12. Поиск диаметра - алгоритм Шеймоса;

  13. Поиск диаметра - альтернативный алгоритм;

  14. Поиск описанного прямоугольника - вращающиеся калиперы;

  15. Приближенный алгоритм построения описанного прямоугольника.

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




  1. Пересечение множества отрезков на плоскости;

  2. Триангуляция разбиением на монотонные многоугольники;

  3. Построение круговой диаграммы видимости;

  4. Пересечение множества полуплоскостей;

  5. Разбиение на выпуклые многоугольники;

  6. Пересечение планарных подразбиений плоскости;

  7. Нахождение ближайшей пары за O(nlogn);

  8. Триангуляция Делоне;

  9. Упорядочивание линий.


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

  1. Ф. Препарата, М. Шеймос. Вычислительная геометрия: введение. М., «Мир», 1989.

  2. M. de Berg, M. Kreveld, M. Overmars. Computational Geometry: Algorithms and Applications. ISBN: 3-540-65620-0, 1998

  3. K. Mulmuley. Computational geometry: an introduction through randomized algorithms. Prentice Hall, 1994.

  4. J. O'Rourke. Computational Geometry in C. ISBN 0-521-64010-5, 1998

Дополнительная:



1. A. Aggraval, B. Chazelle. Parallel computational geometry. Algorithmica, 1988

2. K. Mehlhorn. Data Structures and Efficient Algorithms 3: Multi-dimensional Searching and Computational Geometry. Springer­Verlag, 1984
Каталог: shared -> files


Достарыңызбен бөлісу:




©kzref.org 2022
әкімшілігінің қараңыз

    Басты бет