Дальняя диаграмма Вороного: кто задаёт худший случай

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

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

Есть четыре пункта доставки в углах квадрата и ещё один в его центре. Может ли центральный пункт оказаться самым далёким от склада при каком-нибудь положении склада? Для ближайшего пункта у центра есть собственная ячейка. Для самого далёкого ответ другой: одна из крайних точек всегда не ближе центра. Перестановка слова «ближайший» меняет структуру ответа.

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

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

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

Для точки p дальняя ячейка - множество центров x, где |x-p|≥|x-q| для всех входных точек q. При равенстве центр находится на общей границе, поэтому для однозначного ответа нужен отдельный порядок разрешения равенств. Саму геометрическую границу не следует удалять. После возведения в квадрат общая часть |x|² сокращается. Каждое сравнение задаёт полуплоскость, а пересечение полуплоскостей выпукло.

Почему внутренние точки не дают двумерных ячеек? Внутренняя точка - выпуклая комбинация вершин оболочки. Квадрат расстояния от фиксированного центра - выпуклая функция точки. Её значение внутри не превышает максимального значения на вершинах. Для строго внутренней точки среди различных вершин неравенство строгое хотя бы на одном направлении; такая точка не может стать единственной самой далёкой. Достаточно строить диаграмму по оболочке.

Все непустые двумерные дальние ячейки неограниченны: можно уходить от соответствующей крайней точки в противоположную сторону. Для невырожденного набора диаграмма имеет линейную сложность и строится за O(n log n) вместе с оболочкой. Это не оценка перебора всех пар. Точки на одной прямой и четыре равноудалённые точки требуют аккуратного представления граничных случаев.

Функция R(x)=max |x-p| есть радиус круга с центром x, покрывающего все точки. Её минимум задаётся двумя противоположными граничными точками либо тремя граничными точками. Поэтому центр может лежать на ребре дальней диаграммы, а не обязательно в её вершине. Для кольца нужны ещё r(x)=min |x-p| и ширина R(x)-r(x); обычная диаграмма отвечает за внутреннюю окружность, дальняя - за внешнюю.

Правило

Для минимизации худшего расстояния сохраняй самые далёкие вершины оболочки; кандидаты на охватывающий круг включают двухточечный случай на ребре дальней диаграммы.

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

У квадрата с углами (±2,±2) центр имеет максимальный квадрат расстояния 8. Добавление (0,0) не меняет этот максимум ни в одной точке. Проверим несколько центров, выведем также минимальный квадрат расстояния и допустим равенства среди дальних точек. Программа служит прямым эталоном O(n) на запрос, не строит быструю диаграмму.

from fractions import Fraction

corners = [(-2, -2), (-2, 2), (2, -2), (2, 2)]
points = corners + [(0, 0)]

def distance2(a, b):
    return sum((x - y)**2 for x, y in zip(a, b))

def farthest(center, sites):
    values = [distance2(center, p) for p in sites]
    worst = max(values)
    ids = [i for i, value in enumerate(values) if value == worst]
    return worst, ids

for center in [(0, 0), (3, 0), (1, 2)]:
    radius2, ids = farthest(center, points)
    assert radius2 == farthest(center, corners)[0]
    nearest2 = min(distance2(center, p) for p in points)
    print(center, "R²", radius2, "r²", nearest2, "дальние", ids)

# Две точки: оптимальный центр лежит на целом ребре диаграммы.
a, b = (0, 0), (6, 0)
mid = tuple(Fraction(x + y, 2) for x, y in zip(a, b))
assert distance2(mid, a) == distance2(mid, b)
assert distance2(mid, a) == 9
print("две точки: центр", tuple(map(str, mid)), "R²", 9)
# Любой покрывающий круг имеет диаметр не меньше расстояния AB.
assert distance2(a, b) == 36

(0, 0) R² 8 r² 0 дальние [0, 1, 2, 3]
(3, 0) R² 29 r² 5 дальние [0, 1]
(1, 2) R² 25 r² 1 дальние [0]
две точки: центр ('3', '0') R² 9

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

Возьми только (0,0) и (6,0). Дальняя диаграмма состоит из двух полуплоскостей и прямой x=3, вершин нет. Наименьший охватывающий круг всё равно существует: центр (3,0), радиус 3. Следовательно, перебор только вершин диаграммы пропустит правильный ответ. Двухточечный случай опирается на нижнюю границу: круг, содержащий обе точки, имеет диаметр не меньше расстояния между ними.

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

Ближайшая ячейка центра квадрата непуста, дальняя пуста: переиспользование старого кода без изменения знаков даст противоположную задачу. Нельзя искать минимальную ширину кольца по одному лишь R: круг и кольцо оптимизируют разные функции. Квадраты расстояний подходят для сравнений и поиска дальних точек, но разность квадратов R²-r² не равна ширине R-r и может выбрать другой центр.

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

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

Теперь сам

Для точек (0,0) и (8,0) найди центр и радиус наименьшего охватывающего круга. Появится ли двумерная дальняя ячейка у добавленной точки (3,0)?