Участник:Shersh/Тикеты к вычислительной геометрии (термы 4 и 5) — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Базовые алгоритмы и структуры данных)
Строка 37: Строка 37:
 
#:* Имя функции в \mathrm
 
#:* Имя функции в \mathrm
 
== Базовые алгоритмы и структуры данных ==
 
== Базовые алгоритмы и структуры данных ==
−
# [[Квадродеревья | Квадродерево, сжатое квадродерево]]
+
# [[Квадродеревья | Квадродерево, сжатое квадродерево]] (''10'')
−
# [[ Skip quadtree: определение, время работы | Skip quadtree: определение, время работы, запрос точек в прямоугольнике ]]
+
## А зачем оно надо?
−
# [[ К-d деревья и перечисление точек в произвольном прямоугольнике (статика) | К-d деревья и перечисление точек в произвольном прямоугольнике (статика) ]]
+
## Про перечисление точек в прямоугольнике более формально написать, псевдокод добавить хороший, оценки сказать
−
# [[ Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree) | Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree) ]]
+
## Время работы ортогонального поиска в сжатом квадродереве
−
# [[ Дерево интервалов (interval tree) и пересечение точки с множеством интервалов | Дерево интервалов (interval tree) и пересечение точки с множеством интервалов ]]
+
#:* Убрать текст про билеты вверху
−
# [[ Пересечение прямоугольника с множеством прямоугольников (PST) | Пересечение прямоугольника с множеством прямоугольников (priority search tree) ]]
+
#:* Англоязычные термины
−
# [[ Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree) | Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree) ]]
+
#:* Внутренние ссылки оформить как примечания
 +
#:* Картинки наезжают на заголовки
 +
#:* Оформить правильно источники информации
 +
#:* Добавить категории
 +
# [[Skip quadtree: определение, время работы | Skip quadtree: определение, время работы, запрос точек в прямоугольнике ]]
 +
# [[К-d деревья и перечисление точек в произвольном прямоугольнике (статика)]] (''5'')
 +
## Мы ищем медиану по разным кординатам каждый раз, разве нам достаточно просто как-то посортить точки?
 +
## Более подробное доказательство асимптотики времени работы, разбор случаев, сказать, что оценка довольно грубая, на практике чуть быстрей, хотя всё равно медленно
 +
#:* Оформить правильно англоязычные термины
 +
#:* Оформить правильно источники информации
 +
#:* Отформатировать псевдокод
 +
#:* Функции в тексте взять в \mathrm
 +
#:* Неплохо бы для понимания добавить картинки из гуглящейся презентации
 +
#:* Добавить категории
 +
# [[Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree)]] (''20'')
 +
## Написать в одномерном случае сначала, что его можно решать проще, а в двумерном, что можно использовать простой вариант одномерного в узле
 +
## Картинки очень нужны, без них слабо понятно
 +
## Псевдокоды неплохо бы добавить
 +
## Написать подробно Fractional Cascading с картинками (см. список тем)
 +
#:* Переименовать конспект в Range tree
 +
#:* Заменить знаки неравенств
 +
#:* Заменить вертикальную черту на \mid
 +
#:* Задачу в Шаблон
 +
#:* Все переменные и константы в Tex
 +
#:* Оформить правильно источники информации
 +
#:* Добавить категории
 +
# [[Дерево интервалов (interval tree) и пересечение точки с множеством интервалов]] (''5'')
 +
## Неплохо бы добавить ссылку на код реализации, довольно простая структура
 +
## Можно сказать, как соптимизировать, если нам нужно только количество отрезков
 +
## Картинки было бы неплохо добавить
 +
#:* Переименовать конспект в Interval tree
 +
#:* Определение жирным, англоязычные термины правильно оформить
 +
#:* Отформартировать псевдокод, описать структуру дерева подробней
 +
#:* Добавить Источники информации
 +
#:* Добавить категории
 +
# [[Пересечение прямоугольника с множеством прямоугольников (PST)]] (''5'')
 +
## Картинки добавить
 +
#:* Переименовать конспект в Priority search tree
 +
#:* Логичней сначала писать задачу, а потом давать определение структуры
 +
#:* Отформартировать псевдокоды
 +
#:* Добавить категории
 +
#:* Добавить источники информации
 +
# [[Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree)]] (''5'')
 +
## Чуть подробней написать про решение задачи, как находим, как упорядочиваем отрезки, добавить картинки опять же
 +
#:* Задачу в Шаблон
 +
#:* Правильно оформить англ. термины
 +
#:* Оформить правильно источники информации
 +
 
 
== Аффинное пространство ==
 
== Аффинное пространство ==
 
=== Простые геометрические операции и алгоритмы ===
 
=== Простые геометрические операции и алгоритмы ===

Версия 19:43, 18 февраля 2015

Нумерованные замечания — по содержанию, маркированные — по оформлению

Модель вычислений

Арифметика

  1. Представление чисел с плавающей точкой (5)
    1. Помёрджить с аналогичным конспектом по дискретке
    2. Добавить код получения машинного эпсилон в c++
    • Оформить правильно источники информации
    • Поправить категории
    • Дефисы заменить на тире
    • Заменить знаки неравенств
  2. Интервальная арифметика (10)
    1. Какой-нибудь пример с кодом на c++ (желательно предикат левый поворот) и с объяснением происходящего
    2. И написать, что делать, если в интервальной арифметике посчиталось неточно (добавить просто пример с mpq_class)
    3. Пару мотивационных слов о том, как надо делать вычисления (про скатывание в рациональную), о скорости и т. д.
    • Англоязычные термины
    • В формулы можно добавить пробелы для лучшей читаемости
    • Оформить правильно Источники информации
    • Добавить категории
  3. Adaptive precision arithmetic

Технические подробности

  1. Запуск проекта визуализации cg (10)
    1. Небольшой туториал, как начать работу с библиотекой визуализации, что поставить и как запустить
    2. Неплохо бы ещё скриншоты добавить (чтобы совсем всем всё было понятно)
  2. Туториал по cmake (15)
    1. Сделать конспект более формальным
    2. Как установить, что вообще надо (ссылки добавить)
    3. Простые и последовательные примеры: сборка простого файла, нескольких файлов, как подключить буст, gmp, gtest
    4. Объяснение происходящего в библиотеке визуализации cg
    5. Примеры полных скриптов
    • Добавить категории
    • Добавить ссылок
  3. Тестирование с использованием Google Test (5)
    1. Ссылка на код битая, добавить пример кода с github
    • Задачу в Шаблон
    • Добавить категории
    • Интервики
    • Имя функции в \mathrm

Базовые алгоритмы и структуры данных

  1. Квадродерево, сжатое квадродерево (10)
    1. А зачем оно надо?
    2. Про перечисление точек в прямоугольнике более формально написать, псевдокод добавить хороший, оценки сказать
    3. Время работы ортогонального поиска в сжатом квадродереве
    • Убрать текст про билеты вверху
    • Англоязычные термины
    • Внутренние ссылки оформить как примечания
    • Картинки наезжают на заголовки
    • Оформить правильно источники информации
    • Добавить категории
  2. Skip quadtree: определение, время работы, запрос точек в прямоугольнике
  3. К-d деревья и перечисление точек в произвольном прямоугольнике (статика) (5)
    1. Мы ищем медиану по разным кординатам каждый раз, разве нам достаточно просто как-то посортить точки?
    2. Более подробное доказательство асимптотики времени работы, разбор случаев, сказать, что оценка довольно грубая, на практике чуть быстрей, хотя всё равно медленно
    • Оформить правильно англоязычные термины
    • Оформить правильно источники информации
    • Отформатировать псевдокод
    • Функции в тексте взять в \mathrm
    • Неплохо бы для понимания добавить картинки из гуглящейся презентации
    • Добавить категории
  4. Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree) (20)
    1. Написать в одномерном случае сначала, что его можно решать проще, а в двумерном, что можно использовать простой вариант одномерного в узле
    2. Картинки очень нужны, без них слабо понятно
    3. Псевдокоды неплохо бы добавить
    4. Написать подробно Fractional Cascading с картинками (см. список тем)
    • Переименовать конспект в Range tree
    • Заменить знаки неравенств
    • Заменить вертикальную черту на \mid
    • Задачу в Шаблон
    • Все переменные и константы в Tex
    • Оформить правильно источники информации
    • Добавить категории
  5. Дерево интервалов (interval tree) и пересечение точки с множеством интервалов (5)
    1. Неплохо бы добавить ссылку на код реализации, довольно простая структура
    2. Можно сказать, как соптимизировать, если нам нужно только количество отрезков
    3. Картинки было бы неплохо добавить
    • Переименовать конспект в Interval tree
    • Определение жирным, англоязычные термины правильно оформить
    • Отформартировать псевдокод, описать структуру дерева подробней
    • Добавить Источники информации
    • Добавить категории
  6. Пересечение прямоугольника с множеством прямоугольников (PST) (5)
    1. Картинки добавить
    • Переименовать конспект в Priority search tree
    • Логичней сначала писать задачу, а потом давать определение структуры
    • Отформартировать псевдокоды
    • Добавить категории
    • Добавить источники информации
  7. Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree) (5)
    1. Чуть подробней написать про решение задачи, как находим, как упорядочиваем отрезки, добавить картинки опять же
    • Задачу в Шаблон
    • Правильно оформить англ. термины
    • Оформить правильно источники информации

Аффинное пространство

Простые геометрические операции и алгоритмы

  1. Предикат "левый поворот" (10)
    1. Перенести расчёт погрешности из конспекта про вещественные числа сюда
    2. Сказать, почему в расчёте не используется деление, и что обычно с этим делают
    3. Статью написать именно про предикат поворота, про его сакральный смысл, а не про пересечение отрезков; можно добавить различных применений
    4. Добавить пример, простое правило для запоминания направления
    • Неплохо бы векторные картинки сделать вместо таких растровых
    • Добавить категории
    • Добавить источники информации
  2. Пересечение отрезков и поворот: определение, свойства, вычисление (15)
    1. Подробное и ясное объяснение шагов с картинками (взять часть информации из предиката поворота), вот здесь детальный разбор этой задачи
    2. Про аффинное пространство будет отдельный конспект (если кто-нибудь напишет), поэтому только небольшую справку в начале надо сделать
    3. Рассказать про нахождение самой точки пересечения двух отрезков, и какие проблемы с этим связаны
    • Переменные и константы в Tex
    • Интервики
    • Оформить правильно источники информации
    • Отформатировать псевдокод, оформить как функцию, принимающих два отрезка, код смотреть в cg
    • Добавить категории
  3. Пересечение отрезков на сфере (10)
    1. Доделать конспект: описать всё формально, подробно и понятно
    • Задачу в Шаблон
    • Алгоритм красиво оформить
    • Источники информации
    • Категории
  4. Пересечение окружностей (10)
    1. Добавить расчёт погрешностей (см. список тем)
    2. Переходы бы подробней описать
    • Увеличить дроби
    • Добавить категории
  5. Принадлежность точки выпуклому и невыпуклому многоугольникам (5)
    1. Картинка в случае выпуклого многоугольника
    2. Более подробное объяснение корректности алгоритма в случае невыпуклого полигона
    3. Пару слов про то, работает ли в полигонах с дырками
    • Убрать плашку вверху
    • Оформить правильно источники информации
    • Добавить категории
    • min и max заменить на \min и \max
  6. Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull (10)
    1. См. обсуждения
    2. В некоторых местах не очень понятно, почему это правда - пояснить корректность алгоритма
    3. Про Чена очень мало, смотреть википедию русскую
    • Определение жирным
    • Дефисы на тире
    • Все ссылки в конец, оформить правильно Источники информации
    • Добавить в ссылки примеры кодов (из cg, ещё можно где-нибудь нагуглить)
    • Опустить заголовки на 1, сделать конспект более структурированным
    • Отформатировать псевдокоды

Продвинутые алгоритмы

  1. Динамическая выпуклая оболочка (log^2 на добавление/удаление)
  2. Выпуклая оболочка в n-мерном пространстве
  3. Алгоритм Бентли-Оттмана
  4. Алгоритм Балабана
  5. Трапецоидная карта
  6. Алгоритм Киркпатрика детализации триангуляции
  7. Упрощение полигональной цепи
  8. Ортогональный поиск
  9. Триангуляция полигонов (ушная + монотонная)
  10. Триангуляция многоугольника за n^2
  11. Триангуляция многоугольника заметающей прямой
  12. Пересечение полуплоскостей, связь с выпуклыми оболочками
  13. Пересечение множества отрезков
  14. Snap rounding
  15. Конфигурация
  16. ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых
  17. Пересечение многоугольников (PSLG overlaying)
  18. Локализация в ППЛГ методом полос (персистентные деревья)
  19. Локализация в ППЛГ. Алгоритм Киркпатрика
  20. Трапецоидная карта
  21. BSP-дерево

Скалярное произведение и мера (проверяется)

  1. Диаметр множества точек (вращающиеся калиперы)
  2. Сумма Минковского (определение, вычисление)
  3. Минимальная охватывающая окружность множества точек
  4. Visibility graph и motion planning
  5. Триангуляция Делоне
  6. Диаграмма Вороного
  7. Motorcycle graph
  8. Straight skeleton
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Участник:Shersh/Тикеты_к_вычислительной_геометрии_(термы_4_и_5)&oldid=44892»