Объединение решений

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

Введем обозначение δ для минимума из d{ , (/t ) и d{ rv, rt ).

Настоящий вопрос выглядит так: существуют ли точки q Q и r R, для которых d(q, r) < δ? Если

нет, то ближайшая пара уже была найдена одним из предшествующих рекурсивных вызовов. Если же такие точки существуют, то ближайшие q и r образуют ближай- шую пару в P.

Пусть X* обозначает координату x крайней правой точки в Q, а L — вертикаль- ную линию, описываемую уравнением x = x*. Линия L «отделяет» Q от R. А теперь простой факт:

(5.8) Если существуют q Q и r R, для которых d(q, r) < δ, то каждая из точек q и r располагается в пределах расстояния δ от L.

Доказательство. Предположим, такие q и r существуют; обозначим q = (qx, qy) и r = (rx, ry). Из определения x* следует, что qx < x* < rx. Тогда


и

а это значит, что у каждой из точек q и r координата x находится в пределах δ от x* — и следовательно, ее расстояние от линии L не превышает δ. ■

Итак, чтобы найти ближайшие точки q и r, поиск можно ограничить узкой поло- сой, содержащей только точки P, находящиеся в пределах δ от L. Допустим, это мно- жество обозначается S Л P, а Sy — список, состоящий из точек S, отсортированных по возрастанию координаты у. Один проход по списку Py строит Sy за время O(n).

В контексте множества S утверждение (5.8) переформулируется следующим образом.

(5.9) Существуют q

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Объединение решений:

  1. § 3. Исправление недостатков решения арбитражного суда. Дополнительное решение
  2. 1. Понятие и виды объединений работодателей
  3. 8. Общественные объединения
  4. 6. Объединение работодателей
  5. Право ребенка на объединение
  6. § 5. Общественные объединения
  7. 5. Объединение юридических лиц
  8. 3. Разновидности общественных объединений
  9. 1. Понятие общественного объединения
  10. § 2. Общественные объединения
  11. 2. Права и обязанности членов объединения работодателей
  12. §22. ОБЩЕСТВЕННЫЕ И РЕЛИГИОЗНЫЕ ОРГАНИЗАЦИИ (ОБЪЕДИНЕНИЯ)