Номера вопросов

1. Построение выпуклой оболочки с использованием диаграммы Вороного.

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

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

4. Построение выпуклой оболочки. Заворачивание подарка.

5. Приближенные решения задачи коммивояжера.

6. Построение выпуклой оболочки в трехмерном пространстве.

7. Поиск ближайшей пары точек на плоскости.

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

9. Построение выпуклой оболочки. Метод Грэхема.

10. Поиск ближайшей пары и всех ближайших соседей.

11. Динамическое построение выпуклой оболочки.

12. Построение ЕМОД.

13. Построение выпуклой оболочки с использованием диаграммы Вороного.

14. Основные свойства диаграммы Вороного. Степень вершины равна трем. Внутри окружности нет других точек множества.

15. Основные свойства диаграммы Вороного. Связь с выпуклой оболочкой множества.

16. Выпуклые оболочки. Алгоритм Грэхема.

17. Нахождение ближайшей пары точек на плоскости. Алгоритм. Оценки.

18. Задачи о близости. Области близости. Определение диаграммы Вороного.

19. Поиск ближайшей пары и всех ближайших соседей с использованием диаграммы Вороного.

20. Понятие о нижней оценке трудоемкости. Нижняя оценка для задачи о построении выпуклой оболочки.

21. Выпуклые оболочки. Алгоритм Джарвиса.

22. Алгоритм типа “Разделяй и властвуй”. Условия достижения оценки 0 (n log n).

23. Свойства диаграммы Вороного. Вершина - центр окружности, проходящей через три точки. Внутри окружности нет других точек множества.

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

25. Область близости.

26. Региональный поиск. Алгоритм с предобработкой. Оценки.

27. Локализация точки на планарном подразбиении. Алгоритмы. Оценки.