Кратко — три подхода, сравнение по сложности, устойчивости и предложения для курса.
1) Простой перебор (эвклидов подход)
- Идея: вычислить расстояние для каждой пары точек и взять максимум.
- Реализация: для точек $p_i=(x_i,y_i)$ сравнивать $d^2(p_i,p_j)=(x_i-x_j{)}^2+(y_i-y_j{)}^2$ (использовать квадрат расстояния, чтобы избежать корня).
- Сложность по времени: $O(n^2)$, по памяти: $O(1)$.
- Устойчивость к ошибкам: прост в реализации, но численно чувствителен к переполнению при целых больших координатах и к погрешностям при очень близких значениях; использование 64‑бит целых или суммирования в двойной точности и сравнение квадратичных расстояний с учётом $\epsilon$ уменьшит проблемы.
- Плюсы: простота, детерминированность, не требует предварительной сортировки.
- Минусы: скорлупит при больших $n$.
2) Метод через выпуклую оболочку (двухэтапный)
- Идея: диаметр множества задаётся двумя вершинами выпуклой оболочки (теорема). Сначала строим оболочку, затем ищем максимум среди вершин оболочки.
- Построение оболочки: алгоритмы Грэма или Andrew (monotone chain) дают время $O(n\log n)$ (если точки заранее неотсортированы). Если точки уже отсортированы по x — можно в $O(n)$.
- После получения оболочки с $m$ вершинами можно:
a) сделать перебор пар на оболочке — $O(m^2)$ (плохо, если оболочка крупная),
b) использовать ротирующие калиперы — даёт $O(m)$ дополнительного времени.
- Общая сложность с ротирующими калиперами: $O(n\log n+m)$ (обычно $O(n\log n)$, так как $m\le n$).
- Устойчивость к ошибкам: точность построения оболочки критична — ориентационный предикат (знак перекрёстного произведения) должен быть надёжным: $\text{cross}(a,b,c)=(b_x-a_x)(c_y-a_y)-(b_y-a_y)(c_x-a_x)$. Рекомендуется использовать целочисленные вычисления при целых входных данных или точные предикаты (Shewchuk) для плавающей арифметики.
- Плюсы: asymptotically эффективен; сокращает число кандидатов.
- Минусы: сложнее реализовать корректно для вырожденных случаев (коллинеарность, дубликаты).
3) Ротирующие калиперы (rotating calipers)
- Идея: после построения выпуклой оболочки пройти по парам антиподальных вершин, поддерживая касательные — за линейное время по числу вершин оболочки найти все потенциально максимальные пары.
- Корректность: теорема об антиподальных парах гарантирует, что диаметр обнаружится среди проверенных пар.
- Время: если оболочка есть, то $O(m)$; вместе с построением оболочки — $O(n\log n)$.
- Устойчивость: как и для оболочки — зависит от корректной обработки ориентационных тестов, коллинеарности и повторных вершин. В числах с плавающей точностью нужно аккуратно сравнивать угловые/косинусные критерии с $\epsilon$.
- Плюсы: оптимально и практично для плоскости.
- Минусы: требует аккуратной реализации при вырожденных входах.
Сравнение по критериям (коротко)
- Время: перебор $O(n^2)$ vs оболочка+калиперы $O(n\log n)$ (на практике быстрее уже при умеренных $n$).
- Память: все методы $O(1)$ дополнительной памяти кроме хранения точек и оболочки $O(m)$.
- Устойчивость к ошибкам: перебор — проще управлять; оболочка/калиперы — быстрее, но требуют надёжных геометрических предикатов.
- Чувствительность к выбросам: диаметр очень чувствителен к выбросам (одному удалённому пункту). Для робастности нужны альтернативы (см. ниже).
Возможные улучшения и варианты (для практики и курса)
- Избегать вычисления корня: работать с квадратами расстояний $d^2$.
- Использовать точные предикаты (Shewchuk) или 128‑бит/целые арифметические типы для ориентаций и сравнений при целых координатах.
- Предварительная фильтрация: отсечь точки внутри минимального ограничивающего прямоугольника/контуров, чтобы уменьшить $n$ перед постройкой оболочки.
- При огромных данных: применять приближённые алгоритмы (farthest‑point sampling, коreset'ы) для быстрого приближённого диаметра с гарантией $(1+\delta )$.
- Простые ускорения: spatial hashing, KD‑tree для эвристического отсечения пар в переборе.
- Обработка вырожденных случаев: все точки коллинеарны ($m\le 2$), дубликаты — удалять перед расчётом.
Рекомендации по включению в учебную программу
- Структура модуля (последовательность занятий):
1) Теория: определение диаметра, доказательство, что максимальная пара — вершины выпуклой оболочки.
2) Практика 1: реализация перебора, тестирование на маленьких наборах.
3) Алгоритм оболочки: реализация Andrew/Graham, обработка коллинеарности и дубликатов.
4) Ротирующие калиперы: доказательство корректности и реализация.
5) Тестирование и отладка: случаи с коллинеарностью, одинаковыми точками, большим диапазоном координат.
6) Продвинутые темы: точные предикаты, приближённые методы, влияние выбросов.
- Лабораторные работы: сравнение времени и ошибок на синтетических и реальных наборах; визуализация (оболочка, антиподальные пары).
- Задания для глубины: доказать теорему об антиподальных парах; реализовать вариант с целой арифметикой; оценить влияние $\epsilon$ на результаты.
- Рекомендуемые библиотеки для демонстрации и для сравнения реализации: CGAL (точные предикаты), Shapely/GEOS (практика в Python — но с плавающей арифметикой).
Короткий итог: для обучения и практики начать с перебора (понятность), затем перейти к вычислению выпуклой оболочки и ротирующим калиперам (эффективность). Обязательно разобрать численную устойчивость (точные предикаты, квадраты расстояний) и вырожденные/шумные случаи.