Вопросы к экзамену по вычислительной геометрии

Вопросы к экзамену по «Вычислительной геометрии»
для третьего курса (май 2014)

1. Бинарное дерево отрезков.

2. Реберный список с двойными связями.

3. Задачи регионального поиска, подсчёт точек в регионе. Доминирование.

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

5. Принадлежность точки внутренней области выпуклого и звёздного многоугольника, предварительная обработка.

6. Локализация точки на планарном подразбиении. Метод полос.

7. Локализация точки на планарном подразбиении. Метод цепей.

8. Регуляризация плоского прямолинейного графа.

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

10. Метод Грэхема.

11. Метод Джарвиса.

12. Распараллеливание алгоритма построения выпуклых оболочек.

13. Диаграмма Вороного.

14. Триангуляция Делоне. Её свойства.

15. Жадный алгоритм построения триангуляции Делоне.

16. Получение триангуляции Делоне из произвольной триангуляции.

17. Связь триангуляции Делоне и диаграммый Вороного.