Список тем

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

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

• Как устроены числа с плавающей точкой?

  Представление_вещественных_чисел

  Представление_чисел_с_плавающей_точкой

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

  презентация в csклубе

• Интервальная арифметика. Длинная арифметика. ESSA.

  Интервальная_арифметика

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

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

• Adaptive precision арифметика.

  Adaptive_precision_arithmetic

  статья Шевчука

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

• Предикат пересечения отрезков.

  Предикат_"левый_поворот"

• Пересечение множества отрезков (Bentley-Ottmann).

  Алгоритм_Бентли-Оттмана

• Представление конфигураций плоскости (DCEL). Конфигурация множества прямых на плоскости. Конфигурация множества отрезков на плоскости.

  Конфигурация

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

• Локализация в выпуклом многоугольнике. Локализация в многоугольнике общего вида. Геометрический хеш.

  Wikipedia — Geometric hashing — на лекции не был, посмотрите, мало ли это не то.

• Алгоритм Киркпатрика.

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

• Трапецоидная карта.

  [2]

• Инкрементальная локализация на дереве отрезков.

• Может, тут все-таки имелось в виду дерево интервалов?

• Метод полос.

  Wikipedia — Point location

tip: Это имеет отношение к персистентным деревьям.

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

• Алгоритм Джарвиса.

  [3]

• Алгоритм Эндрюса-Грэхема.

  [4]

• Выпуклая оболочка как аналог merge sort (слияние двух непересекающихся оболочек).

  этот вроде как раз подойдет

• Выпуклая оболочка как аналог quick sort (без дополнительной памяти).

  [5]

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

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