Вопросы по вычислительной геометрии (комбинаторные алгоритмы), 2009 год

1. 
   Преобразуемость задач. Нижние и верхние оценки. Примеры.
   
2. 
   Геометрические примитивы в алгоритмах вычислительной геометрии. Векторное произведение.
   
3. 
   Выпуклая оболочка. Нижняя граница сложности.
   
4. 
   Выпуклая оболочка. Алгоритм Грэхема. Модификации.
   
5. 
   Выпуклая оболочка. Алгоритм Джарвиса. Анализ среднего случая.
   
6. 
   Выпуклая оболочка. Быстрый алгоритм (QuickCH).
   
7. 
   Выпуклая оболочка. Быстрый алгоритм на основе сбалансированного разделения и слияния. Модификация с “мостиками”.
   
8. 
   Выпуклая оболочка. Быстрый алгоритм на основе сбалансированного разделения и слияния – оценка сложности.
   
9. 
   Выпуклая оболочка. Алгоритм Киркпатрика-Сайделя (Prune & Search).
   
10. 
    Оценка сложности алгоритма Киркпатрика-Сайделя.
    
11. 
    Алгоритм нахождения медианы (метод Prune & Search).
    
12. 
    Выпуклая оболочка. Алгоритм Чена.
    
13. 
    Оценка сложности алгоритма Чена.
    
14. 
    Рандомизированный алгоритм построения выпуклой оболочки (на плоскости).
    
15. 
    Построение выпуклой оболочки в реальное время.
    
16. 
    Представление линейных упорядоченных списков (сцепляемых очередей) рандомизированными деревьями (Treaps).
    
17. 
    Построение выпуклой оболочки множества точек в трехмерном пространстве.
    
18. 
    Аппроксимация выпуклой оболочки.
    
19. 
    Выпуклая оболочка простого многоугольника. Алгоритм Ли.
    
20. 
    Диаметр множества точек. Нижняя граница.
    
21. 
    Диаметр множества точек. Алгоритм.
    
22. 
    Геометрический поиск. Задача регионального поиска (подсчет). Метод локусов. Предобработка. Запрос.
    
23. 
    Задача локализации точки. Принадлежность многоугольнику. Метод луча. Выпуклый многоугольник. Звездный многоугольник.
    
24. 
    Свойства планарных графов. Представление планарных графов (РСДС).
    
25. 
    Локализация точки на планарном подразбиении. Метод полос.
    
26. 
    Локализация точки на планарном подразбиении. Метод цепей.
    
27. 
    Локализация точки на планарном подразбиении. Метод детализации триангуляции.
    
28. 
    Метод детализации триангуляции. Анализ сложности.
    
29. 
    Локализация точки на планарном подразбиении. Метод трапеций Зайделя (пошаговый алгоритм).
    
30. 
    Региональный поиск. Метод квадрантного дерева.
    
31. 
    Метод квадрантного дерева. Анализ сложности.
    
32. 
    Региональный поиск. Метод 2-D дерева. Анализ.
    
33. 
    Метод 2-D дерева. Анализ сложности
    
34. 
    Дерево отрезков. Метод дерева регионов в задаче регионального поиска.
    
35. 
    Задача единственности элементов как вычислительный прототип. Нижняя граница сложности.
    
36. 
    Задачи о близости (Ближайшая пара, Все ближайшие соседи, Евклидово МОД, Триангуляция, Поиск ближайшего соседа). Нижние оценки.
    
37. 
    Задача о ближайшей паре. Метод сбалансированного разделения и слияния.
    
38. 
    Диаграмма Вороного. Определение, свойства. Триангуляция Делоне.
    
39. 
    Представление планарного графа реберным списком с двойными связями.
    
40. 
    Построение диаграммы Вороного. Алгоритм сбалансированного разделения и слияния Шеймоса и Хоуи (Shaimos & Hoey).
    
41. 
    Построение диаграммы Вороного. Алгоритм с заметанием (Fortune).
    
42. 
    Алгоритм с заметанием (Fortune). Структуры данных.
    
43. 
    Нижняя оценка для построения диаграммы Вороного. Решение задач о близости с помощью диаграммы Вороного.
    
44. 
    Решение задачи о Евклидовом МОД.
    
45. 
    Задача о пересечении отрезков на плоскости. Алгоритм с заметанием.
    
46. 
    Алгоритм пересечения отрезков на плоскости.
    

Литература

1. 
   [ПШ] Препарата Ф., Шеймос М. Вычислительная геометрия: Введение.- М.: Мир, 1989.-478 с. (Franco P.Prerarata, Michael Ian Shamos. Computational Geometry: An Introduction. Springer-Verlag, 1985). (http://algolist.manual.ru/maths/geom/index.php - в конце раздела)
   

2. 
   [Л ] Майкл Ласло. Вычислительная геометрия и компьютерная графика на С++.-М.: "Издательство БИНОМ", 1997.-304 с. (Michael J. Laszlo. Computational Geometry and Computers Graphics in C++. Prentice-Hall, 1996)
   
3. 
   Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦМНО, 1999.- 960 с.
   

1. 
   Красным цветом выделены «теоретические» вопросы.
   
2. 
   Черным курсивом помечены остальные вопросы, при ответе на которые подразумевается использование демонстрационных программ (визуализаторов).