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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (линк на ESSA)
м (rollbackEdits.php mass rollback)
 
(не показаны 4 промежуточные версии 4 участников)
Строка 34: Строка 34:
 
* Метод полос.
 
* Метод полос.
 
*: [http://en.wikipedia.org/wiki/Point_location Wikipedia — Point location]
 
*: [http://en.wikipedia.org/wiki/Point_location Wikipedia — Point location]
 +
::tip: Это имеет отношение к персистентным деревьям.
  
 
=== Выпуклые оболочки на плоскости. ===
 
=== Выпуклые оболочки на плоскости. ===
Строка 39: Строка 40:
 
* Алгоритм Джарвиса.
 
* Алгоритм Джарвиса.
 
*: [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]
* Алгоритм Эндрюса-Грэма.
+
* Алгоритм Эндрюса-Грэхема.
 
*: [http://nms.lcs.mit.edu/~aklmiu/6.838/convexhull/]
 
*: [http://nms.lcs.mit.edu/~aklmiu/6.838/convexhull/]
 
* Выпуклая оболочка как аналог merge sort (слияние двух непересекающихся оболочек).
 
* Выпуклая оболочка как аналог merge sort (слияние двух непересекающихся оболочек).
Строка 52: Строка 53:
 
* Выпуклая оболочка множества окружностей одинакового радиуса.
 
* Выпуклая оболочка множества окружностей одинакового радиуса.
 
* Выпуклая оболочка множества окружностей разного радиуса.
 
* Выпуклая оболочка множества окружностей разного радиуса.
 +
 +
[[Категория: Вычислительная геометрия]]

Текущая версия на 19:39, 4 сентября 2022

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

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

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

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

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

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

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

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

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

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

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

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