Учитывая n точек на контуре единичного круга, я хочу вычислить ближайшие 2 точки.
Точки не упорядочены, и мне нужно сделать это за O (n) (поэтому я не могу сортировать их по часовой стрелке...)
Когда-то я знал решение для этого, но забыл его... решение включает в себя хеширование и разбиение круга на n или более фрагментов.
Если вы нашли алгоритм для расчета только расстояния, а не конкретных точек, этого будет достаточно.
Вот решение, которое претендует на O(n log log n) для нахождения ближайшей пары точек на линии. Это тривиальное преобразование из вашей задачи - каждая точка (x, y) на единичной окружности отображается в линейную координату x' в отрезке [0,2pi), где x' = atan2(y,x). Идея, после того как вы преобразовали ее в одномерную задачу, примерно состоит в том, чтобы начать хэшировать координаты x в сегменты, перераспределяя большие сегменты на сегменты меньшего размера, пока не останется не более одной точки на сегмент, затем пройтись по списку и найти ближайшая пара. (И у вас будет одна дополнительная проверка, чтобы увидеть, образуют ли точки с минимальной и максимальной координатами x' еще более тесную пару, чем линейный минимум.)
Отсортируйте их по углу, поместив в ячейки (binsort, O(n)); выберите количество ячеек того же порядка, что и количество точек. Затем пройдите и найдите ближайшую пару, повторяя процесс в ячейке, если в нее попадает более одной точки.
O(N log N). Мое предложение такое же, как и предложение @Jim Lewis, на которое ссылается; Я не знаю, как они получают O(N log log N); в случайном случае вы ожидаете уменьшения количества точек для проверки на (e-2)/e за O(N) шага (если вы выберете # бинов = # точек (свойство распределения Пуассона)), и геометрический ряд этого равно 1/(1-e/(e-2)) = (e-2)/2, что является постоянным коэффициентом.
- person Rex Kerr; 17.09.2010
