Список тем (year 2012) — различия между версиями
(Новая страница: «===Устойчивая реализация алгоритмов вычислительной геометрии.=== * Как устроены числа с пл...») |
м (rollbackEdits.php mass rollback) |
||
(не показано 12 промежуточных версий 3 участников) | |||
Строка 1: | Строка 1: | ||
+ | ==Осенний семестр== | ||
+ | * Кратчайший путь O(n^2). Overmars and Welzl’s Algorithm & rotation tree. [[Visibility_graph_и_motion_planning#Overmars_and_Welzl.E2.80.99s_Algorithm]] | ||
+ | |||
+ | ==Пройденное за весенний семестр== | ||
+ | Материалы можно найти в [https://www.dropbox.com/sh/i8ka1e4dr7girdh/AABgCA2Y8RYym90xJNO_m7Wka dropbox] (там есть README - в котором есть некоторая индексация конспекта) | ||
+ | |||
+ | * [[Пересечение_отрезков_на_сфере]] (доделать) | ||
+ | * Пересечение двух выпуклых многоугольников (лекция 01_1) | ||
+ | * Задача о разделении многоугольника на два равновеликих (лекции 01_3, 02_2) | ||
+ | * Обобщение триангуляции полигонов на случаи с дырками (лекции 02_1-02_2, 03_4) (добавить в триангуляцию - [[Триангуляция_полигонов_(ушная_%2B_монотонная)]]) | ||
+ | * Персистентные структуры (лекция 04_*) | ||
+ | *: персистентный список за амортизированное O(1) | ||
+ | *: персистентные деревья (с ревизиями) | ||
+ | * Локализация точки в многоугольнике (лекция 04_*) (доделать статью - [[Локализация_в_ППЛГ_методом_полос_(персистентные_деревья)]]) | ||
+ | * Локализация прямоугольника среди прямоугольников (перечислить всех, имеющих с ним хоть одну общую точку) (Большой объем. Все три шага. Наверное можно эту тему взять с кем-нибудь, поделив шаги и баллы.) (лекции 04_*, 05_*, 06_*) | ||
+ | * Fractional Cascading (лекция 05_*) ([https://github.com/PolarHare/Fractional-Cascading/blob/master/src/Problem16E.java пример кода]) (написать подробно с картинками тут - [[Перечисление_точек_в_произвольном_прямоугольнике_за_n_*_log_%5E(d_-_1)_n_(range_tree)#Fractional_cascading]]) | ||
+ | |||
+ | ==То, что можно доделать с прошлого года== | ||
+ | Возможно есть еще что-то, тут все, что я нашел на скорую руку с этих ссылок: | ||
+ | * [[Вычислительная_геометрия]] | ||
+ | * [[Список_тем]] | ||
+ | |||
+ | ===Неотсортированные темы.=== | ||
+ | * Пересечение окружностей - можно рассчитать погрешность тут: | ||
+ | *: [[Пересечение_окружностей]] | ||
+ | |||
===Устойчивая реализация алгоритмов вычислительной геометрии.=== | ===Устойчивая реализация алгоритмов вычислительной геометрии.=== | ||
− | + | * Расчет погрешности вычисления предиката (на примере вычисления предиката поворота). | |
− | |||
− | |||
− | * Расчет погрешности вычисления предиката (на примере вычисления предиката поворота) | ||
*: [http://compsciclub.ru/node/1563 презентация в csклубе] | *: [http://compsciclub.ru/node/1563 презентация в csклубе] | ||
− | * | + | * Дописать ESSA в Интервальную арифметику. |
*: [[Интервальная_арифметика]] | *: [[Интервальная_арифметика]] | ||
− | *: | + | *: ESSA: [http://pages.cpsc.ucalgary.ca/~marina/papers/Segment_intersection.ps] |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
=== Выпуклые оболочки на плоскости. === | === Выпуклые оболочки на плоскости. === | ||
− | + | Я упустил, эти алгоритмы описаны здесь: [[Статические_выпуклые_оболочки:_Джарвис,_Грэхем,_Эндрю,_Чен,_QuickHull]] | |
− | * Алгоритм Джарвиса. | + | * <del>Алгоритм Джарвиса. (доделать - картинки, возможно пояснения)</del> |
+ | *: [[Алгоритмы_построения_выпуклых_оболочек_множества_точек_на_плоскости]] | ||
*: [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B6%D0%B0%D1%80%D0%B2%D0%B8%D1%81%D0%B0] | *: [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B6%D0%B0%D1%80%D0%B2%D0%B8%D1%81%D0%B0] | ||
− | * Алгоритм Эндрюса-Грэхема. | + | * <del>Алгоритм Эндрюса-Грэхема.</del> |
+ | *: [[Алгоритмы_построения_выпуклых_оболочек_множества_точек_на_плоскости]] | ||
*: [http://nms.lcs.mit.edu/~aklmiu/6.838/convexhull/] | *: [http://nms.lcs.mit.edu/~aklmiu/6.838/convexhull/] | ||
* Выпуклая оболочка как аналог merge sort (слияние двух непересекающихся оболочек). | * Выпуклая оболочка как аналог merge sort (слияние двух непересекающихся оболочек). | ||
+ | *: Дописать сюда: [[Статические_выпуклые_оболочки:_Джарвис,_Грэхем,_Эндрю,_Чен,_QuickHull]] | ||
*: [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D0%B8%D1%80%D0%BA%D0%BF%D0%B0%D1%82%D1%80%D0%B8%D0%BA%D0%B0 этот вроде как раз подойдет] | *: [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D0%B8%D1%80%D0%BA%D0%BF%D0%B0%D1%82%D1%80%D0%B8%D0%BA%D0%B0 этот вроде как раз подойдет] | ||
− | * Выпуклая оболочка как аналог quick sort (без дополнительной памяти). | + | * <del>Выпуклая оболочка как аналог quick sort (без дополнительной памяти).</del> |
+ | *: [[Алгоритмы_построения_выпуклых_оболочек_множества_точек_на_плоскости]] | ||
*: [http://www.cs.princeton.edu/courses/archive/spr10/cos226/demo/ah/QuickHull.html] | *: [http://www.cs.princeton.edu/courses/archive/spr10/cos226/demo/ah/QuickHull.html] | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
[[Категория: Вычислительная геометрия]] | [[Категория: Вычислительная геометрия]] |
Текущая версия на 19:19, 4 сентября 2022
Осенний семестр
- Кратчайший путь O(n^2). Overmars and Welzl’s Algorithm & rotation tree. Visibility_graph_и_motion_planning#Overmars_and_Welzl.E2.80.99s_Algorithm
Пройденное за весенний семестр
Материалы можно найти в dropbox (там есть README - в котором есть некоторая индексация конспекта)
- Пересечение_отрезков_на_сфере (доделать)
- Пересечение двух выпуклых многоугольников (лекция 01_1)
- Задача о разделении многоугольника на два равновеликих (лекции 01_3, 02_2)
- Обобщение триангуляции полигонов на случаи с дырками (лекции 02_1-02_2, 03_4) (добавить в триангуляцию - Триангуляция_полигонов_(ушная_+_монотонная))
- Персистентные структуры (лекция 04_*)
- персистентный список за амортизированное O(1)
- персистентные деревья (с ревизиями)
- Локализация точки в многоугольнике (лекция 04_*) (доделать статью - Локализация_в_ППЛГ_методом_полос_(персистентные_деревья))
- Локализация прямоугольника среди прямоугольников (перечислить всех, имеющих с ним хоть одну общую точку) (Большой объем. Все три шага. Наверное можно эту тему взять с кем-нибудь, поделив шаги и баллы.) (лекции 04_*, 05_*, 06_*)
- Fractional Cascading (лекция 05_*) (пример кода) (написать подробно с картинками тут - Перечисление_точек_в_произвольном_прямоугольнике_за_n_*_log_^(d_-_1)_n_(range_tree)#Fractional_cascading)
То, что можно доделать с прошлого года
Возможно есть еще что-то, тут все, что я нашел на скорую руку с этих ссылок:
Неотсортированные темы.
- Пересечение окружностей - можно рассчитать погрешность тут:
Устойчивая реализация алгоритмов вычислительной геометрии.
- Расчет погрешности вычисления предиката (на примере вычисления предиката поворота).
- Дописать ESSA в Интервальную арифметику.
- Интервальная_арифметика
- ESSA: [1]
Выпуклые оболочки на плоскости.
Я упустил, эти алгоритмы описаны здесь: Статические_выпуклые_оболочки:_Джарвис,_Грэхем,_Эндрю,_Чен,_QuickHull
-
Алгоритм Джарвиса. (доделать - картинки, возможно пояснения) -
Алгоритм Эндрюса-Грэхема. - Выпуклая оболочка как аналог merge sort (слияние двух непересекающихся оболочек).
-
Выпуклая оболочка как аналог quick sort (без дополнительной памяти).