Аннотация. Курс посвящен основным алгоритмам вычислительной геометрии, используемым в самых разных приложениях геометрии, в т.ч. c omputer vision , геоинформатика, биоинформатика, стереовидение и т.п.
I. Введение: 2 ч.
Предмет вычислительной геометрии. Используемая модель вычислений. Индивидуальные и массовые запросы. Сложность алгоритма: время ответа на запрос, затраты памяти, время на предварительную обработку. Многоугольники: простые, выпуклые, звездные. Ядро звездного многоугольника. Задача о принадлежности точки простому, выпуклому, звездному многоугольнику.
II. Выпуклые оболочки: 4 ч.
Определение выпуклой оболочки (ВО) множества точек на плоскости. Нижняя оценка сложности ее построения. Наивный алгоритм построения ВО множества точек на плоскости. Понятие общего положения. Вырожденные случаи. Понятие устойчивости алгоритма (robustness). Модифицированный метод Грэхема. Нижняя оценка сложности построения ВО множества точек на плоскости. Другие алгоритмы построения ВО множества точек на плоскости: метод обхода Грэхема; метод заворачивания подарка (метод Джарвиса) - алгоритм, чувствительный к выходу (output sensitive); инкрементный алгоритм; метод <<разделяй и властвуй>> (с предварительной сортировкой точек и без нее); <<быстрая оболочка>>; алгоритм Чена. Выбор наиболее подходящего алгоритма с учетом конкретной ситуации.
III. Пересечение отрезков и наложение планарных подразбиений: 4 ч.
Задача о нахождении всех пересечений отрезков из заданного множества. Нижняя оценка сложности: проверка наличия двух пересекающихся отрезков в заданном множестве. Нахождение пересечений отрезков методом плоского заметания. Реберный список с двойными связями (РСДС). Плоский прямолинейный граф (ППЛГ). Планарное подразбиение. Задача наложения (overlay) планарных подразбиений и алгоритм ее решения. Частные случаи: пересечение выпуклых многоугольников; пересечение простых многоугольников.
IV. Триангуляция многоугольника: 4 ч.
Диагональ простого многоугольника: определение и лемма о существовании. Триангуляция простого многоугольника: определение, лемма о существовании, сложность (количество треугольников в триангуляции). Наивный алгоритм построения триангуляции простого многоугольника. Граф, двойственный триангуляции: определение и свойства. Построение триангуляции простого многоугольника путем <<отрезания ушей>>. 3-раскрашиваемость графа триангуляции простого многоугольника. Задача о картинной галерее. Монотонные многоугольники. Разбиение простого многоугольника на y-монотонные. Построение триангуляции монотонного многоугольника. Триангуляция произвольных многоугольников и ППЛГ.
V. Локализация точки на планарном подразбиении: 4 ч.
Постановка задачи. Метод полос и оценка его сложности. Метод детализации триангуляции Киркпатрика и оценка его сложности. Трапецоидальная карта (trapezoidal map): определение, сложность, представление. Вероятностный алгоритм построения трапецоидальной карты. Оценка ожидаемого времени построения трапецоидальной карты, ожидаемого размера поисковой структуры данных (search structure) и ожидаемого времени обработки запроса на локализацию точки.
VI. Диаграмма Вороного и триангуляция Делоне: 6 ч.
Определение и основные свойства диаграммы Вороного множества точек на плоскости. Наивный алгоритм построения диаграммы Вороного. Нижняя оценка сложности построения диаграммы Вороного. Оптимальные алгоритмы построения диаграммы Вороного: метод плоского заметания, метод <<разделяй и властвуй>>. Возможности обобщения понятия диаграммы Вороного.
Определение и свойства триангуляций множества точек на плоскости. Легальные (legal) триангуляции: определение и построение. Граф Делоне и его свойства. Триангуляция Делоне. Вероятностный алгоритм построения триангуляции Делоне и анализ его сложности.
VII. Конфигурации прямых на плоскости и двойственность: 4 ч.
Задача о вычислении расхождения (discrepancy). Двойственность точек и прямых. Конфигурации (arrangements) прямых на плоскости: определение, сложность, инкрементный алгоритм построения. Понятие зоны прямой в конфигурации; теорема о зоне (Zone Theorem). Оценка сложности инкрементного алгоритма построения конфигурации. Понятие уровня (level) точки в конфигурации прямых. Вычисление уровней вершин конфигурации и их связь с величиной расхождения.
Информация для желающих запрограммировать алгоритмы построения выпуклой оболочки множества точек на плоскости и/или триангуляции простого многоугольника.
Cистема автоматического тестирования решений доступна по следующей ссылке:
На данный момент, имеется возможность протестировать алгоритмы построения выпуклой оболочки.
Для доступа к системе необходимы имя пользователя (Team login - присваивается индивидуально; пожалуйста, напишите мне, если Вы хотите его получить), пароль (Password - 54321, общий для всех пользователей) и идентификатор контеста (Contest ID - 091027_geom).
Конфигурации прямых на плоскости и двойственность.
14 November - 20 November
14 ноября - последняя лекция
Содержание лекции:
Задача планирования пути (motion planning) на плоскости при наличии полигональных препятствий:
- для точечного робота;
- для полигонального робота (общие идеи).
Граф видимости (visibility graph): определение и алгоритм построения. Использование графа видимости для нахождения кратчайшего пути между двумя точками на плоскости.
Вероятностный алгорим построения минимальной описанной окружности для множества точек на плоскости.
Нахождение диаметра множества точек. Разбиение простого многоугольника на выпуклые многоугольники.
Во время подготовки к ответу разрешается пользоваться любыми материалами (однако общение не допускается). После начала ответа пользоваться нельзя ничем.
Определения, основные свойства рассматриваемых геометрических структур и несложные алгоритмы, обсуждавшиеся на лекциях, необходимо знать наизусть.
Знание пунктов программы, не вошедших в явном виде в список вопросов к экзамену/зачету, может потребоваться при ответе на дополнительные вопросы.
Для желающих сдать экзамен 28 ноября:
Если Вы запрограммировали и протестировали алгоритмы построения выпкулой оболочки множества точек на плоскости и/или триангуляции простого многоугольника и хотели бы получить на этом основании "льготы" на экзамене, пришлите мне, пожалуйста краткий отчет о практической деятельности, содержащий указание того, какие алгоритмы были запрограммированы, результаты тестирования и программный код. Код должен быть читабельным; в частности, он должен содержать необходимые для его понимания комментарии. Отчет должен быть представлен не позднее 27 ноября, 18:00.
Очередная возможность для сдачи экзамена/зачета - 12 декабря, 10:00.
Вниманию запрограммиовавших предложенные алгоритмы и желающих получить на данном основании льготы на зачете/экзамене: пришлите мне, пожалуйста, отчет о Вашей работе не позднее 11 декабря, 18:00. Детали см. в предыдущем комментарии.
12 December - 18 December
Крайний срок представления программных реализаций алгоритмов построения выпуклой оболочки множества точек на плоскости и триангуляции простого многоугольника - 18 декабря, 18:00. В указанное время контест 091027_geom будет закрыт.
19 December - 25 December
26 December - 1 January
Очередная сдача зачета/экзамена состоится в субботу, 23 января, в ПОМИ РАН. Начало - в 10:00.
