Геометрия (26-е мая 2025)

  1. Геометрия-1
    1. Две ближайшие точки за O(n) (рандомизированный инкрементальный).
    2. Локализация точки за [O(n), O(logn)].
    3. Разбиение планарного графа на грани (сортировка по углу и dfs). В контексте локализации точки.
    4. Биекция между задачами "выпуклая оболочка" и "пересечение полуплоскостей".
    5. Построение выпуклой оболочки за O(nlogk) и за O(n/k * sort(k)).
− Перерыв −
  1. Геометрия-2. DavidMount
    1. Выпуклые оболочки в больших размерностях и simplex. Пример на 2n точках, где граней 2n. Алгоритм проверки вершин: для каждой бахнем simplex.
    2. Выбрать k точек : диаметр выбранных точек минимален. Кстати, это задача с чемпионата мира.
    3. Минимальный покрывающий точки круг за O(n).
    4. Для каждой точки на плоскости найти ближайшую за O(n3/2), за O(nlogn).
    5. MST на плоскости за O(nlogn).
    6. Диаграма Вороного и триангуляция Делоне за O(n2).
    7. Диаграма Вороного и триангуляция Делоне за O(nlogn).
    8. Триангуляция Делоне строится за O(sort(n)), выпуклая оболочка за Ω(sort(n)).
    9. Сумма Минковского. Пример задачи "погода": дан вып-многоугольник-туча и вып-многоугольник-аэропорт, тучу сносит с постоянной скоростью, когда перестанут пересекаться? а найти min t(v), где v − направление?
− Перерыв −
  1. Геометрия и структуры данных
    1. Dynamic Convex Hull : строим верхнюю огибающую, дерево отрезков, для объединения нужна общая касательная, умеют за O(logn).
    2. Число точек в полуплоскости.
      1. Решение с предподсчётом за O(n2 log n) и O(log n) на запрос.
      2. Масштабирование решения: O(n3/2 log n) на предподсчёт, O(n1/2 logn) на запрос.
      3. Идея с квадродеревом: nlogС на предподсчёт, n0.7925 на запрос.
      4. Объединяем идеи: сверху квадродерево, на кусках размера m прекалк с персистентностью, меньшее число кусков нужно обсчитывать.
      5. Идея с выбором угла и 4 из 6 вместо 3 из 4.
    3. Motion Planning : провести робота (выпуклый k-угольник) через мир с многоугольными препятствиями (n, N).
      1. Видим граф (какая-то из k вершин робота совпадает с какой-то из N вершин препятствия)
      2. Применяем Минковского: N → N + nk; строим граф за O((N+nk)3).
      3. Строим граф быстрее: O((N+nk)*sort(N+nk))
      4. А как решать для невыпуклых? Триангуляция невыпуклых (n,N) → N треугольников
      5. А как решать быстрее? Разделяй и властвуй и merge многоугольников. youtube