Структура данных для хранения подквадратов

Высокоуровневое описание алгоритма зависит от возможности назвать подквадрат Sst и быстро определить, какие точки P содержатся в нем (если они есть). Словарь — наиболее естественная структура данных для реализации таких операций.

Универсальное множество U возможных элементов представляет собой множество всех подквадратов, а множество S, хранимое в структуре данных, состоит из подквадратов с точками из множества P’, встречавшимися до настоящего момента. А конкретно, для каждой точки p’ Ѯ P’ в словаре хранится подквадрат,  содержащий ее, вместе с индексом p’. Заметим, что  в общем случае намного больше количества точек n. Таким образом, данная ситуация напоминает ту, что была описана в разделе 13.6 для хеширования: универсальное множество возможных элементов (множество всех подквадратов) намного больше количества индексируемых элементов (подквадраты, содержащие входные точки, которые уже встречались).

Затем, при рассмотрении следующей точки p в случайном порядке, определяется содержащий ее подквадрат Sst и выполняется операция Lookup для каждого из 25 подквадратов, близких к Sst. Для всех точек, обнаруженных этими операциями Lookup, вычисляется расстояние до p. Если ни одно из этих расстояний не меньше δ, то ближайшее расстояние не изменяется; мы вставляем Sst (вместе c p) в словарь и переходим к следующей точке.

Но если будет найдена точка p’, для которой δ‘ = d(p, p’) < δ, то ближайшую пару необходимо обновить. Обновление приводит к весьма масштабным последствиям: так как расстояние ближайшей пары уменьшилось с δ до δ‘, вся коллекция подквадратов вместе с поддерживающим ее словарем становится бесполезной — ведь она приносит пользу только в том случае, если минимальное расстояние равно δ.

Соответственно мы вызываем MakeDictionary для создания нового, пустого словаря, в котором хранятся подквадраты с длиной стороны δ‘/2. Для каждой точки, встреченной до настоящего момента, мы определяем содержащий ее подквадрат (в новом наборе подквадратов), после чего вставляем этот подквадрат в словарь.

После того как это будет сделано, можно переходить к вставке следующей точки в случайном порядке.