Билеты по курсу вычислительной геометрии

1. Skip quadtree: определение, время работы

2. Пересечение прямоугольника с множеством прямоугольников:

   • range tree + fractional cascading;
   • k-d tree.

3. Пересечение прямоугольника с множеством прямоугольников:

   • interval tree;
   • priority search tree;

4. Триангуляция многоугольника. Существование, ушная триангуляция.

   Пересечение прямоугольника с множеством непересекающихся отрезков:

   • segment tree;

5. Аффинное пространство. Пересечение отрезков и поворот: определение, свойства. Объём

6. Фильтрованное вычисление предиката поворота.

7. Статические выпуклые оболочки на плоскости. Джарвис, Грэм, Эндрю, Чен,

   QuickHull. Оболочка многоугольника, оболочка полилинии.

8. Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление)

   Выпуклая оболочка в n-мерном пространстве. Quick-hull и вероятностный алгоритм.

9. Триангуляция многоугольника заметающей прямой

10. ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых

11. Локализация в ППЛГ.

    • методом полос (персистентные деревья);
    • Киркпатрик.

12. Трапецоидная карта.

13. Сумма Минковского (определение, вычисление)

    • два выпуклых многоугольника
    • два невыпуклых многоугольника

14. Сумма Минковского

    • выпуклый и невыпуклый многоугольники

15. Диаметр множества точек (вращающиеся калиперы)

    Минимальная охватывающая окружность множества точек. Вероятностный алгоритм.

16. Граф видимости и планирование движения.

    • построение графа видимости заметающим лучом;
    • сокращение графа видимости;
    • построение навигационного графа на трапецоидной карте;
    • планирование маршрута невыпуклого тела с вращением (без суммы Минковского).

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

    • статический алгоритм
    • существование;
    • приводимость любой триангуляции флипами к ТД;
    • эквивалентность критерия Делоне для треугольников критерию для ребер.

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

    • динамический алгоритм: удаление и вставка

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

    • динамический алгоритм: локализация

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

    • определение и свойства;
    • алгоритм построения ДВ множества точек.

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

    • диаграмма Вороного высших порядков, построение;
    • связь с подразбиением Делоне (ближайший и дальнейший);

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

    Пересечение многоугольников (PSLG overlaying)

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

24. Пересечение множества отрезков.