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



Скачать 58.29 Kb.
Дата08.10.2012
Размер58.29 Kb.
ТипРабочая программа

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




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






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


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

Введение. О чем наука. Сложности: 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

Похожие:

Программа дисциплины вычислительная геометрия Цели изучения дисциплины iconДисциплины История Общая трудоемкость изучения дисциплины составляет 3 зачетных единицы (108 часов). Цели и задачи дисциплины
Целью изучения дисциплины является: формирование у студентов комплексного представления культурном своеобразии России, ее месте в...
Программа дисциплины вычислительная геометрия Цели изучения дисциплины iconПримерная программа дисциплины " компьютерная геометрия и графика"
В результате изучения дисциплины “Компьютерная геометрия и графика” студентом должны быть приобретены следующие знания, умения и...
Программа дисциплины вычислительная геометрия Цели изучения дисциплины iconРабочая Программа учебной дисциплины дпп. Дс. 03 Польский язык цели изучения дисциплины

Программа дисциплины вычислительная геометрия Цели изучения дисциплины iconРабочая Программа учебной дисциплины опд. В. 03 Польский язык цели изучения дисциплины

Программа дисциплины вычислительная геометрия Цели изучения дисциплины iconПрограммы учебной дисциплины «Риторика» Цели и задачи дисциплины
Целью изучения дисциплины является: получение представления о практической риторике как коммуникативной дисциплины на основе фундаментальных...
Программа дисциплины вычислительная геометрия Цели изучения дисциплины iconРабочая программа дисциплины " Геометрия " предназначена для студентов 1 курса по специальности
Требования к уровню подготовки студента, завершившего изучение дисциплины "Геометрия"
Программа дисциплины вычислительная геометрия Цели изучения дисциплины icon1. Цели и задачи дисциплины Целью изучения дисциплины является
Целью изучения дисциплины является получение представления о психологической стороне делового общения Задачами дисциплины являются:...
Программа дисциплины вычислительная геометрия Цели изучения дисциплины iconРабочая программа дисциплины «Геометрия» Направление: 010100. 62 «Математика» Подготовка
Рабочая программа дисциплины «Геометрия» [Текст]/Сост. Артамкин И. В, Бурман Ю. М гу-вшэ.–Москва.–2009.–14 с
Программа дисциплины вычислительная геометрия Цели изучения дисциплины iconУчебной дисциплины «Математика и информатика» для направления подготовки 035700. 62 Лингвистика
Целью изучения дисциплины является Задачами дисциплины являются: Требования к уровню освоения содержания дисциплины Процесс изучения...
Программа дисциплины вычислительная геометрия Цели изучения дисциплины icon1. Цели и задачи дисциплины, ее место в системе подготовки аспиранта, требования к уровню освоения содержания дисциплины
Цель изучения дисциплины – Изучение теории и практики разделения минеральных частиц в гравитационных полях
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org