*: [[Интервальная_арифметика]]
*: ESSA: [http://pages.cpsc.ucalgary.ca/~marina/papers/Segment_intersection.ps]
===Конфигурации пространства. Определение и построение.===
* Предикат пересечения отрезков.
*: [[Предикат_"левый_поворот"]]
* Пересечение множества отрезков (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: Это имеет отношение к персистентным деревьям.
=== Выпуклые оболочки на плоскости. ===
* Алгоритм Джарвиса.(доделать - картинки, возможно пояснения)*: [[Алгоритмы_построения_выпуклых_оболочек_множества_точек_на_плоскости]]
*: [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://nms.lcs.mit.edu/~aklmiu/6.838/convexhull/]
* Выпуклая оболочка как аналог merge sort (слияние двух непересекающихся оболочек).
*: [[Алгоритмы_построения_выпуклых_оболочек_множества_точек_на_плоскости]]
*: [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 (без дополнительной памяти).
*: [[Алгоритмы_построения_выпуклых_оболочек_множества_точек_на_плоскости]]
*: [http://www.cs.princeton.edu/courses/archive/spr10/cos226/demo/ah/QuickHull.html]
=== Типовые задачи ===
* Расписать погрешность предиката (например, поворот отрезка и точки пересечения двух отрезков).
* Пересечение множества окружностей разного радиуса.
* Выпуклая оболочка множества окружностей одинакового радиуса.
* Выпуклая оболочка множества окружностей разного радиуса.
[[Категория: Вычислительная геометрия]]
