#algorithm #geometry
#алгоритм #геометрия
Вопрос:
Укажите нижнюю границу времени n log n для алгоритма, чтобы проверить, имеет ли набор точек специальную точку k.
k определяется как:
для множества точек A, если для каждой точки m в A существует точка q в A такая, что k находится в середине отрезка mq, такое k не обязательно должно принадлежать A.
Например, этот набор имеет специальную точку k = (0.5, 0.5) для набора из четырех точек (1,0), (0,1), (1,1), (0,0).
Я был совершенно невозмутим, когда они спросили меня об этом, мне ничего не пришло в голову. Я думаю, для этого нужен сильный геометрический фон.
Комментарии:
1. Я не совсем понимаю ваш вопрос. Алгоритм, который находит нижнюю границу? Вы имеете в виду алгоритм с нижней границей? Или доказательство того, что любой такой алгоритм имеет такую нижнюю границу?
Ответ №1:
O(nlogn) решение (Я все еще не понимаю, почему вы ищете решение с нижней границей. Вы могли бы также просто выполнить исчерпывающую проверку, а затем просто запустить цикл nlogn, чтобы убедиться в нижней границе. Не очень сложно. Я думаю, вы должны иметь в виду верхнюю границу):
Найдите единственную допустимую точку-кандидат, усреднив все точки. Т.е. суммируя их координаты и деля на количество точек. Если такое k существует, это оно. Если такого k не существует, мы обнаружим, что найденная точка недействительна на последнем шаге.
Создайте новый массив (набор) точек, где мы сдвигаем наши оси так, чтобы они были сосредоточены на точке k. Т.е. если k = (x k, y k), точка (x, y) станет (x-x k, y-y k). Сортируйте точки в соответствии с отношением x / y и нормой sqrt (x2 y2). Как показывает следующий шаг, не имеет значения, как выполняется эта сортировка, т. Е. Какой критерий является основным, а какой второстепенным.
Мы могли бы искать дополнение к каждой точке или, что еще лучше, просто пройти по массиву и убедиться, что каждые две соседние точки действительно являются дополнениями. Т.е. если это решение, то каждые две дополнительные точки в этом новом массиве имеют вид (x, y) и (-x,-y), поскольку мы перецентрировали наши оси, что означает, что они имеют одинаковое соотношение («градиент») и норму, и послесортировка, должна быть смежной.
Если k недопустимо, то есть точка, к которой мы придем в этом обходе, и обнаружим, что ее сосед не имеет правильной / дополнительной формы ==> такого k нет.
Время =
O(n) для нахождения кандидата k
O(n) для построения нового массива, поскольку каждая новая точка может быть вычислена за O (1)
O(nlogn) для сортировки
O(n) для проверки обхода
= O(nlogn)
Ответ №2:
Я бы сказал, что вы просто вычисляете центр масс (сначала удалив дубликаты) и проверяете, ваш ли он k . Вероятно, единственной причиной этого был O(n log n) бы поиск точки в указанном местоположении.