Поиск ближайшей пары точек на плоскости с неразличимыми координатами x за O(nlogn)

Большинство реализаций алгоритма поиска ближайшей пары точек на плоскости, которые я видел в Интернете, имеют один из двух недостатков: либо они не соответствуют времени выполнения O(nlogn), либо они не подходят для случая, когда некоторые точки имеют общую координату x. Является ли хеш-карта (или эквивалентная) обязательный оптимальной для решения этой проблемы?

Грубо говоря, рассматриваемый алгоритм (согласно CLRS Ch. 33.4):

1. Для массива точек P создайте дополнительные массивы X и Y, чтобы X содержал все точки P, отсортированные по координате x, а Y содержал все точки P, отсортированные по координате y.
2. Разделите точки пополам - проведите вертикальную линию, чтобы разделить X на два массива, X_L и X_R, и разделите Y аналогичным образом, чтобы Y_L содержал все точки слева от линии, а Y_R содержал все точки справа от линия, обе отсортированы по координате y.
3. Сделайте рекурсивные вызовы для каждой половины, передав X_L и Y_L одной и X_R и Y_R другой, и найдите минимальное расстояние г в каждой из этих половин.
4. Наконец, определите, есть ли пара с одной точкой слева и одной точкой справа от разделительной линии с расстоянием меньше г; с помощью геометрического аргумента мы обнаруживаем, что можем принять стратегию простого поиска в следующих 7 точках для каждой точки на расстоянии г от разделительной линии, что означает, что рекомбинация разделенных подзадач занимает всего O (n) шаг (даже если это выглядит n² на первый взгляд).

Это имеет некоторые сложные граничные случаи. Один из способов справиться с этим — сортировать полосу точек на расстоянии г от разделительной линии на каждом этапе рекомбинации (например, здесь), но известно, что это приводит к решению O (nlog²n).

Другой способ, которым люди справляются с пограничными случаями, — это предположить, что каждая точка имеет отдельную координату x (например, здесь): обратите внимание на фрагмент в ближайшем Util, который добавляет к Pyl (или Y_L, как мы его называем), если координата x точки в Y <= линия или Pyr (Y_R) в противном случае. Обратите внимание: если все точки лежат на одной вертикальной линии, это приведет к тому, что мы запишем за конец массива в C++, поскольку мы записываем все точки н в Y_L.

Таким образом, сложный момент, когда точки могут иметь одну и ту же координату x, заключается в разделении точек в Y на Y_L и Y_R в зависимости от того, находится ли точка п в Y в X_L или X_R. Псевдокод в CLRS для этого (слегка отредактированный для краткости):

for i = 1 to Y.length
    if Y[i] in X_L
        Y_L.length = Y_L.length + 1;
        Y_L[Y_L.length] = Y[i]
    else Y_R.length = Y_R.length + 1;
        Y_R[Y_R.length] = Y[i]

Однако в отсутствие псевдокода, если мы работаем с простыми массивами, у нас нет волшебной функции, которая может определить, находится ли Y[i] в ​​X_L за время O(1). Если мы уверены, что все координаты x различны, конечно, мы знаем, что все, у кого координата x меньше разделительной линии, находится в X_L, поэтому одним сравнением мы знаем, на какой массив разбить любую точку п в Y на . Но в случае, когда x-координаты не обязательно различны (например, в случае, когда все они лежат на одной вертикальной линии), нужна ли нам хеш-карта, чтобы определить, находится ли точка в Y в X_L или X_R, и успешно взломать вниз Y в Y_L и Y_R за время O(n)? Или есть другая стратегия?