1. Приоритетная очередь. Пирамидальная сортировка. Алгоритм быстрой сортировки. Алгоритм нахождения к-го наименьшего элемента. Красные-Черные деревья данных.
2. Метод заметающей прямой. Алгоритм Бентли-Отмана нахождения пересечений отрезков на плоскости.
3. Алгоритм локализации точки на планарном подразбиении методом полос.
4. Алгоритм локализации точки на планарном подразбиении методом цепей.
5. Алгоритм триангуляции простого многоугольника. Задача об оптимальном освещении (The Art Gallery problem).
6. Алгоритм локализации точки на планарном подразбиении методом детализации триангуляции.
7. Алгоритм локализации точки на планарном подразбиении методом трапеций.
8. Дерево отрезков.
9. Алгоритм нахождения площади объединения прямоугольников.
10. 2-D-деревья. Алгоритм регионального поиска с помощью 2-D-дерева.
11. Дерево регионов. Алгоритм регионального поиска с помощью дерева регионов. Техника частичного каскада.
12. Дерево интервалов. Алгоритм нахождения всех интервалов, содержащих заданную точку.
13. Алгоритм нахождения всех отрезков на плоскости, пересекающих заданное окно.
14. Алгоритм перечисления всех пересекающихся пар изотетичных прямоугольников.
15. Построения выпуклой оболочки методом обхода Грэхема.
16. Построения выпуклой оболочки методом обхода Джарвиса.
17. Быстрый метод построения выпуклой оболочки.
18. Построения выпуклой оболочки методом «разделяй и властвуй».
19. Алгоритм построения выпуклой оболочки в реальном времени.
20. Структура данных для поддержки динамической выпуклой оболочки.
21. Структура данных «Пирамида Фибоначчи». Алгоритм Дийкстры .
22. Алгоритм построения кратчайшего пути в простом многоугольнике с препятствиями.
23. Алгоритм И.Балабана нахождения пересечений отрезков на плоскости.
24. Построение графа видимости для М точек, лежащих в простом многоугольнике без дыр.

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

1. Ф.Препарата, М.Шеймос, Вычислительная геометрия. Введение. Изд. «Мир», 1989.
2. M.Berg, M. van Kreveld, M.Overmars, O.Schwarzkopf, Computational Geometry. Algorithms and Applications. Springer-Verlag, 1998.
3. T.H.Cormen, C.E.Leiserson, R.L.Rivest, C.Stein, Introduction to Algorithms, MIT Press, 2001. Имеется русский перевод.
4. А.Ахо, Дж.Хопкрофт, Дж.Ульман, Построение и анализ вычислительных алгоритмов. Изд. «Мир», 1979.

Наверх