Симплексный поиск: запрос с наклонной границей

Если механизм уже знаком - листай до «Теперь сам».

Как думаешь: что нужно сохранить

Прямоугольное окно kd-дерева легко проверяется по координатам. Но камера может смотреть под углом: область интереса стала треугольником. Поможет ли повернуть оси один раз? Для одного фиксированного направления - иногда. Если каждый следующий запрос повернут по-своему, заранее выбранная система координат не выровняет все границы.

На что это похоже

Представь склад, где на каждом ящике написана область, покрывающая все его товары на карте. Если поисковый треугольник накрыл ящик целиком, можно прибавить весь счётчик, не открывая его. Если прошёл мимо - ящик пропускается. Открывать приходится только ящики, которые граница разрезала. Поэтому хороший склад оценивается не одинаковым размером ящиков, а числом ящиков вдоль произвольной линии разреза.

Механизм: от определения к алгоритму

В двумерной геометрии симплекс - треугольник; в размерности d это выпуклая оболочка d+1 аффинно независимых точек. Здесь задача - подсчитать или перечислить входные точки, попавшие в замкнутый треугольник. Он является пересечением трёх полуплоскостей. Проверять принадлежность можно по одинаковому знаку трёх ориентированных площадей.

Симплициальное разбиение делит набор на r непересекающихся по точкам групп близкого размера и заключает каждую группу в треугольник. Сами треугольники могут перекрываться: потребовать геометрического разбиения плоскости означало бы добавить лишнее условие. Теорема о разбиении гарантирует, что любая прямая пересекает внутренности лишь O(√r) охватывающих треугольников. Построй такое разбиение рекурсивно для каждой группы.

В узле лежат охватывающая область, число точек и ссылки на детей. Если область целиком внутри запроса, для подсчёта прибавь её размер. Если снаружи - ничего. Иначе спускайся. Три прямые границы пересекают O(√r) областей с точностью до констант. Рекуррентность имеет вид Q(n)≤c√r·Q(2n/r)+O(r) для фиксированного r. Константа c и множитель 2 не исчезают из доказательства сами по себе. Выбрав достаточно большое постоянное r, получают показатель 1/2+ε.

В книге именно эта конструкция даёт линейную память и время запроса O(n^(1/2+ε)), а не буквально O(√n). Более сильные результаты требуют другой конструкции. Нижнюю границу Ω(√n) для числа канонических подмножеств в обсуждаемой модели нельзя объявлять нижней границей любого мыслимого алгоритма: важны модель памяти и разрешённые операции. Для перечисления нужно дополнительно +k, поскольку каждую найденную точку придётся хотя бы записать в ответ.

Правило

Оценивай число групп, пересекаемых границей, а не только высоту дерева; для простого дерева разбиения сохраняй ε в показателе оценки.

Разбор: проследим вычисление

Ниже прямой эталон принадлежности треугольнику. Его сложность линейна по числу входных точек; он не реализует теорему о разбиении. Зато им можно проверять ответы будущего индекса, включая вершины и точки на сторонах. Второй порядок вершин проверяет, что знак ориентации не зависит от того, как пользователь перечислил углы.

def orient(a, b, p):
    return ((b[0] - a[0]) * (p[1] - a[1])
            - (b[1] - a[1]) * (p[0] - a[0]))

def inside(triangle, p):
    a, b, c = triangle
    assert orient(a, b, c) != 0
    signs = [orient(a, b, p), orient(b, c, p),
             orient(c, a, p)]
    return min(signs) >= 0 or max(signs) <= 0

triangle = [(0, 0), (6, 0), (0, 6)]
points = [(1, 1), (3, 3), (5, 5), (-1, 0), (0, 0)]
answer = [p for p in points if inside(triangle, p)]
assert answer == [p for p in points
                  if inside(triangle[::-1], p)]
print("ответ", answer)
# Счётчик целиком принятой группы: все её точки внутри.
group = [(1, 1), (2, 1), (1, 2)]
assert all(inside(triangle, p) for p in group)
print("принятая группа", len(group))
# Наивная замена треугольника прямоугольником неверна.
box = [p for p in points if 0 <= p[0] <= 6 and 0 <= p[1] <= 6]
print("лишние в прямоугольнике", sorted(set(box) - set(answer)))

ответ [(1, 1), (3, 3), (0, 0)]
принятая группа 3
лишние в прямоугольнике [(5, 5)]

Разбор: где проходит граница

Охватывающий прямоугольник треугольника пропускает точку (5,5), хотя 5+5>6. Если сначала найти точки в прямоугольнике, а затем отфильтровать треугольник, ответ будет правильным, но время может стать линейным при пустом итоговом результате. Большинство точек может лежать в срезанных углах. Это показывает разницу между корректностью обёртки и обещанной асимптотикой запроса.

Что ломается без этого

Если считать перекрывающиеся охватывающие треугольники отдельными копиями точек, в ответе появятся дубликаты: разбиение должно разделять именно набор данных. Если принимать группу только потому, что её центр внутри, можно принять внешние точки. Если убрать ε из доказанной оценки, тест на маленьком наборе этого не обнаружит: ошибка находится в утверждении о росте, а не в отдельном численном ответе.

Зачем это в работе

Такие запросы возникают при выборе объектов в треугольном секторе обзора, проверке линейных ограничений и геометрических преобразованиях задач поиска. Для небольших наборов прямой эталон проще и надёжнее сложной структуры. Индекс оправдан, когда набор статичен, запросов много и стоимость подготовки окупается. Раздельно измеряй подготовку, пустые запросы и запросы с большим ответом: стоимость выдачи маскирует поиск.

Теперь сам

Треугольник (0,0),(4,0),(0,4), точки (1,1),(2,2),(3,3). Сколько точек внутри, если граница включена? Может ли группа с одной внешней точкой приниматься целиком?