Вращающиеся калиперы

Диаметр множества - наибольшее расстояние между двумя его точками. Перебор пар стоит $O(n^2)$, но обе точки диаметра обязательно лежат на выпуклой оболочке, а по оболочке можно пройти двумя указателями.

Почему концы диаметра на оболочке

Если точка $A$ лежит строго внутри оболочки, её можно сдвинуть в сторону от $B$, оставаясь внутри, - и расстояние вырастет. Значит максимум достигается на вершинах.

Два указателя

Идём по стороне $p_i p_{i+1}$ и держим вершину $j$, наиболее удалённую от этой стороны. Когда сторона поворачивается, самая удалённая вершина сдвигается только вперёд - отсюда линейность.

int j = 1;
for (int i = 0; i < m; i++) {
    int ni = (i + 1) % m;
    while (std::abs(cross(h[ni] - h[i], h[(j+1) % m] - h[i])) > std::abs(cross(h[ni] - h[i], h[j] - h[i])))
        j = (j + 1) % m;
    best = std::max({best, dist2(h[i], h[j]), dist2(h[ni], h[j])});
}

Сравниваем удвоенные площади вместо расстояний - это целые числа, и никакой точности не теряется. Ответ тоже удобнее хранить как квадрат расстояния: он целый.

Проверено перебором: на 2000 случайных наборов до 30 точек калиперы дали тот же квадрат диаметра, что и полный перебор пар.

Вырожденные случаи

Оболочка из одной или двух точек ломает цикл - для неё ответ считается напрямую. Это же относится к набору, где все точки совпали или лежат на одной прямой: оболочка выродится в отрезок.

Что ещё считают калиперами

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

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

Смежное

• Выпуклая оболочка;
• Ближайшая пара точек.