В этом параграфе вы разберёте классическую задачу вычислительной геометрии: как найти пару ближайших точек на плоскости. Вы узнаете, почему полный перебор всех пар неэффективен, и научитесь решать эту задачу за , применяя стратегию «Разделяй и властвуй». Такой подход часто встречается в олимпиадных и прикладных задачах на двумерные данные.
Ключевые вопросы параграфа
- Почему перебор всех пар точек работает медленно и как этого избежать?
- Как устроен алгоритм поиска ближайшей пары с помощью деления и сканирования полосы?
- Как добиться точного и стабильного результата при вычислениях с вещественными числами?
Задача
Ваша задача — найти ближайшую пару точек из заданного множества.
В компьютерных графике и зрении есть множество вариантов применения этой задачи из вычислительной геометрии. Примитивный алгоритм с квадратичным временем выполнения делает итерации, проходя через все пары точек, чтобы найти ближайшие друг к другу. Ваша цель — спроектировать алгоритм «разделяй и властвуй», время выполнения которого составит .
Решение
- Чтобы решить эту задачу за время , разобьём с помощью правильно подобранной вертикальной линии данные точек пополам — множества и размера .
- Ради простоты предположим, что все координаты для данных точек различные и количество точек чётное.
- С помощью двух рекурсивных вызовов с параметрами и мы находим минимальные расстояния и в этих поднаборах. Пусть .
Остаётся проверить, существуют ли такие точки и , при которых расстояние между ними меньше . Мы не можем себе позволить проверять все возможные такие пары, так как их . Для более быстрой проверки мы отбросим все точки из и , расстояние которых от центральной линии по больше, чем . Таким образом, мы сосредотачиваемся на следующей полосе:
Остановитесь и подумайте:
Почему мы можем сузиться до этой полосы?
Теперь отсортируем точки из полосы по координатам и обозначим получившийся отсортированный список . Оказывается, что если , то расстояние между точками и однозначно будет больше . Упражнение ниже это демонстрирует.
Упражнение
Разделите полосу на квадратов, как показано ниже, и продемонстрируйте, что каждый из таких квадратов содержит максимум четыре точки ввода.
Это приводит к следующему алгоритму.
- Сначала мы сортируем данные нам точек по их координатам , затем делим получившийся отсортированный список на две половины и размера .
- Находим минимальные расстояния и с помощью рекурсивных вызовов для каждого из наборов и . Пусть .
- Тем не менее наша работа ещё не закончена, потому что нам также нужно найти минимальное расстояние между точками из разных наборов (то есть точкой из и точкой из ) и проверить, ниже ли это расстояние, чем .
- Чтобы в этом убедиться, мы отфильтруем изначальный набор и оставим только точки с дистанцией по до средней линии, не превышающей .
- После этого мы сортируем набор точек в получившейся линии по координатам и сканируем получившийся список.
- Вычислим расстояние от каждой точки до семи последующих точек списка и вычислим — минимальное расстояние, которое нам встретилось во время сканирования.
- Затем выведем .
Время выполнения алгоритма соответствует рекуррентному соотношению.
— результат сортировки точек в полосе по координате при каждой итерации.
Упражнение
Проанализируйте рекурсивное дерево алгоритма и докажите, что .
Упражнение
Продемонстрируйте, как избежать сортировки при каждом рекурсивном вызове и понизить время выполнения до .*
- Формат ввода: Первая строка содержит точек. Каждая из следующих строк определяет точку .
- Формат вывода: Минимальное расстояние.
- Ограничения: ; — целые числа.
- Примеры
Пример 1
|
Ввод |
Вывод |
|
2 |
5.0 |
Пример 2
|
Ввод |
Вывод |
|
11 |
1.414213 |
- Во втором примере самое маленькое расстояние — . Есть две пары точек на этом расстоянии. Ниже они выделены голубым и красным: и ; и .
Помните, что расстояние между точками и равно . Так, хотя ввод и содержит только целые числа, ответ не обязательно будет целым числом, и потому вам нужно обратить внимание на точность при выводе результатов. Абсолютное значение разницы между ответом вашей программы и оптимальным значением не должно превышать . Для этого ваш ответ должен содержать не меньше четырех цифр в дробной части. Иначе даже правильно вычисленный результат может не пройти нашу систему проверки из-за ошибок при округлении.
Совет: по возможности старайтесь избегать использования чисел с плавающей дробной частью, при необходимости используйте встроенные алгоритмы для сортировки.
✅ Получилось разобраться, как найти пару ближайших точек быстрее, чем за ?
Что дальше
Теперь вы умеете находить пару ближайших точек на плоскости с помощью алгоритма «Разделяй и властвуй». Вы увидели, как сортировка, аккуратное разбиение и сканирование узкой полосы позволяют снизить сложность задачи до , сохранив точность вычислений.
Далее — заключительный параграф главы: мы кратко подведём итоги и соберём воедино все стратегии, с которыми вы познакомились.
А пока вы не ушли дальше — закрепите материал на практике:
- Отметьте, что урок прочитан, при помощи кнопки ниже.
- Пройдите мини-квиз, чтобы проверить, насколько хорошо вы усвоили тему.
- Перейдите к задачам этого параграфа и потренируйтесь.
- Перед этим — загляните в короткий гайд о том, как работает система проверки.
Хотите обсудить, задать вопрос или не понимаете, почему код не работает? Мы всё предусмотрели — вступайте в сообщество Хендбука! Там студенты помогают друг другу разобраться.
Ключевые выводы параграфа
- Задачу нахождения пары ближайших точек можно решить не за , а за , если использовать стратегию «Разделяй и властвуй».
- Алгоритм включает сортировку точек по координате, рекурсивное деление множества и слияние с анализом узкой полосы шириной .
- При слиянии достаточно проверить не все пары, а только точки в полосе, отсортированные по второй координате, — это снижает число сравнений.
- Точная реализация требует аккуратности: важно корректно обрабатывать базовые случаи, следить за порядком точек и не упустить минимум.