Подготовка рекурсии

Начнем с нескольких простых подготовительных операций. Было бы очень удобно, если бы каждый рекурсивный вызов для множества P' !Ξ P начинался с двух списков: списка P'x, в котором все точки P' отсортированы по возрас- танию координаты х, и списка P'y, в котором все точки P' отсортированы по возрастанию координаты у.
Для этого можно воспользоваться описанным ниже алгоритмом.

Еще перед началом рекурсии все точки P сортируются по координате х , а потом по координате у; так получаются списки Px и Py. С каждым элементом списка связана запись с информацией о позиции точки в обоих списках.

Первый уровень рекурсии работает так, как описано ниже; другие уровни работают полностью аналогично. О определяется как множество точек в первых >/2' позициях списка Px («левая половина»), а R — как множество точек в других \чП\ позициях списка Pх («правая половина»); схема разбиения представлена на рис. 5.6. За один проход по Px и Py за время O(n) можно создать четыре списка: Qx с точками Q, отсортированными по возрастанию координаты х; Qy с точками Q, отсортированными по возрастанию координаты y; и два аналогичных списка Rx и Ry. Для каждого элемента каждого из этих списков также хранится его позиция в обоих исходных списках.

Затем рекурсивно определяется ближайшая пара точек в О (с обращениями к спискам Ox и (2v). Предположим, (/„ и ⅞, (правильно) возвращены как ближай- шая пара точек в Q. Аналогичным образом определяется ближайшая пара точек в R, обозначим их f;, и fj.

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

Еще по теме Подготовка рекурсии:

  1. ПОДГОТОВКА ПРОФЕССИОНАЛЬНАЯ
  2. Подготовка переговорщиков.
  3. Проблемы подготовки журналистов.
  4. Профессионально-психологическая подготовка (ППП).
  5. Психологическая подготовка к задержанию.
  6. 15.7.2. Подготовка возбуждением
  7. 6.4. Профессионально-психологическая подготовка юриста
  8. 6.3. Морально-психологическая подготовка юриста
  9. Часть 1 ПОДГОТОВКА К ВОССТАНОВЛЕНИЮ ДУШИ
  10. Психологическая подготовка сотрудников к управленческой деятельности
  11. Сущность, цели, задачи подготовки.
  12. Глава IV Психологическая подготовка к юридической деятельности