Список тем (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 в Интервальную арифметику.
 
*: [[Интервальная_арифметика]]
 
*: [[Интервальная_арифметика]]
−
*: {{TODO |t=по ESSA вообще ничего не нашел}}
+
*: ESSA: [http://pages.cpsc.ucalgary.ca/~marina/papers/Segment_intersection.ps]
−
:: - пожалуйста: [http://pages.cpsc.ucalgary.ca/~marina/papers/Segment_intersection.ps]
 
−
* Adaptive precision арифметика.
 
−
*: [[Adaptive_precision_arithmetic]]
 
−
*: [http://www.cs.cmu.edu/~quake/robust.html статья Шевчука]
 
−
 
 
−
===Конфигурации пространства. Определение и построение.===
 
−
* Предикат пересечения отрезков.
 
−
*: [[Предикат_"левый_поворот"]]
 
−
* Пересечение множества отрезков (Bentley-Ottmann).
 
−
*: [[Алгоритм_Бентли-Оттмана]]
 
−
* Представление конфигураций плоскости (DCEL). Конфигурация множества прямых на плоскости. Конфигурация множества отрезков на плоскости.
 
−
*: [[Конфигурация]]
 
  
−
===Конфигурации пространства. Локализация.===
 
−
 
−
* Локализация в выпуклом многоугольнике. Локализация в многоугольнике общего вида. Геометрический хеш.
 
−
*: [http://en.wikipedia.org/wiki/Geometric_hashing Wikipedia — Geometric hashing] — на лекции не был, посмотрите, мало ли это не то.
 
−
* Алгоритм Киркпатрика.
 
−
*:
 
−
<s>[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 Википедия — Алгорити Киркпатика] — что это делает здесь, казалось бы, это надо в выпуклые оболочки.</s> кококо, это все-таки то самое, Препарата, Шамос, страница 75. Всем вычгеом.
 
−
* Трапецоидная карта.
 
−
*: [http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2002/JukkaKaartinen/]
 
−
* Инкрементальная локализация на дереве отрезков.
 
−
:* Может, тут все-таки имелось в виду [http://en.wikipedia.org/wiki/Interval_tree дерево интервалов]?
 
−
* Метод полос.
 
−
*: [http://en.wikipedia.org/wiki/Point_location Wikipedia — Point location]
 
−
::tip: Это имеет отношение к персистентным деревьям.
 
  
 
=== Выпуклые оболочки на плоскости. ===
 
=== Выпуклые оболочки на плоскости. ===
−
 
+
Я упустил, эти алгоритмы описаны здесь: [[Статические_выпуклые_оболочки:_Джарвис,_Грэхем,_Эндрю,_Чен,_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

Осенний семестр

Пройденное за весенний семестр

Материалы можно найти в dropbox (там есть README - в котором есть некоторая индексация конспекта)

То, что можно доделать с прошлого года

Возможно есть еще что-то, тут все, что я нашел на скорую руку с этих ссылок:

Неотсортированные темы.

Устойчивая реализация алгоритмов вычислительной геометрии.


Выпуклые оболочки на плоскости.

Я упустил, эти алгоритмы описаны здесь: Статические_выпуклые_оболочки:_Джарвис,_Грэхем,_Эндрю,_Чен,_QuickHull

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Список_тем_(year_2012)&oldid=84894»