Построение мотоциклетного графа Студент 445 группы Титов Артём Научный руководитель: Вяткина К.В. - презентация

1 Построение мотоциклетного графа Студент 445 группы Титов Артём Научный руководитель: Вяткина К.В.

2 Основные понятия Мотоциклетный граф Eppstein and Erickson, 1998 Прямолинейный скелет Aichholzer et al., 1995

3 Цель будущая [1] Cheng and Vigneron, 2007

4 Цель нынешняя [2] Cheng and Vigneron, 2007

5 Алгоритм Разбиение и события перехода Начальные столкновения Мотоциклетный граф [2] Cheng and Vigneron, 2007

6 Факты Используется в наиболее эффективных методах построения прямолинейного скелета Теоритическая сложность работы алгоритма построение мотоциклетного графа O(nnlogn)

7 А зачем ? Для построения прямолинейного скелета !

8 А зачем нам прямолинейный скелет ? Построение крыши Восстановление поверхности по множеству сечений параллельными плоскостями. Оригами

9 Результат Программа на Java Построение мотоциклетного графа Визуализация процесса построения Набор классов для работы с геометрическими объектами

10 Источники 1. Wikipedia A. Aichholzer, F. Aurenhammer, D. Alberts, B. Gärthner. A novel type of skeleton for polygons. The Journal of Universal Computer Science, 1 (1995) D. Eppstein, J. Erickson. Raising roofs, crashing cycles, and playing pool: applications of a data structure for finding pairwise interactions. Discrete and Computational Geometry Б 22(4) (1999) S.-W. Cheng, A. Vigneron. Motorcycle Graphs and Straight Skeletons. Algorithmica, 47 (2007),