Теоретический алгоритм нахождения ближайших 2 точек на окружности в O (n)

Question

Учитывая n точек на контуре единичного круга, я хочу вычислить ближайшие 2 точки.

Точки не упорядочены, и мне нужно сделать это в O (n) (поэтому я не могуотсортировать их по часовой стрелке ...)

Когда-то я знал решение для этого, но забыл его ... решение включает в себя хеширование и разбиение круга на n или более фрагментов.

Если вынашел алгоритм для расчета только расстояния, а не конкретных точек, он будет достаточно хорош ..

Answer 1

Вот решение , которое подразумевается как O (n log log n) для поиска ближайшей пары точек на линии. Это тривиальное преобразование вашей проблемы - каждая точка (x, y) на единичной окружности отображается на линейную координату x 'в отрезке линии [0,2pi), где x '= atan2 (y, x). Идея, как только вы преобразовали ее в одномерную задачу, заключается в примерно, чтобы начать хэширование координат х 'в сегменты, перераспределяя большие сегменты в ведра поменьше, пока не будет не более одной точки на ведро, затем просмотрите список и найти ближайшую пару. (И у вас будет еще одна проверка, чтобы увидеть, если точки с координатами min и max x 'образуют еще более близкую пару, чем линейная минимум.)

Answer 2

Сортируйте их по углу, помещая их в контейнеры (бинсор, O(n));выберите количество бинов того же порядка, что и количество точек.Затем пройдите и найдите ближайшую пару, повторяя процесс внутри корзины, если в нее попадает более одной точки.