Список тем — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Выпуклые оболочки на плоскости.)
м (линк на ESSA)
Строка 8: Строка 8:
 
*: [[Интервальная_арифметика]]
 
*: [[Интервальная_арифметика]]
 
*: {{TODO |t=по ESSA вообще ничего не нашел}}
 
*: {{TODO |t=по ESSA вообще ничего не нашел}}
 +
:: - пожалуйста: [http://pages.cpsc.ucalgary.ca/~marina/papers/Segment_intersection.ps]
 
* Adaptive precision арифметика.
 
* Adaptive precision арифметика.
 
*: [[Adaptive_precision_arithmetic]]
 
*: [[Adaptive_precision_arithmetic]]

Версия 20:22, 27 января 2012

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

TODO: по ESSA вообще ничего не нашел

- пожалуйста: [1]

Конфигурации пространства. Определение и построение.

Конфигурации пространства. Локализация.

  • Локализация в выпуклом многоугольнике. Локализация в многоугольнике общего вида. Геометрический хеш.
    Wikipedia — Geometric hashing — на лекции не был, посмотрите, мало ли это не то.
  • Алгоритм Киркпатрика.

Википедия — Алгорити Киркпатика — что это делает здесь, казалось бы, это надо в выпуклые оболочки. кококо, это все-таки то самое, Препарата, Шамос, страница 75. Всем вычгеом.

  • Трапецоидная карта.
    [2]
  • Инкрементальная локализация на дереве отрезков.

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

  • Алгоритм Джарвиса.
    [3]
  • Алгоритм Эндрюса-Грэма.
    [4]
  • Выпуклая оболочка как аналог merge sort (слияние двух непересекающихся оболочек).
    этот вроде как раз подойдет
  • Выпуклая оболочка как аналог quick sort (без дополнительной памяти).
    [5]

Типовые задачи

  • Расписать погрешность предиката (например, поворот отрезка и точки пересечения двух отрезков).
  • Пересечение множества окружностей разного радиуса.
  • Выпуклая оболочка множества окружностей одинакового радиуса.
  • Выпуклая оболочка множества окружностей разного радиуса.