Алгоритм нахождения специальной точки k за O (n log n) времени

Question

Дайте n log n нижнюю границу для алгоритма, чтобы проверить, имеет ли набор точек специальную точку k.

k определяется как:

для набора точек A, если для каждой точки m в A существует точка q в A, такая, что k находится в серединеотрезок mq такой ak не обязательно должен принадлежать A.

Например, этот набор имеет специальную точку k = (0,5, 0,5) для набора из четырех точек (1,0), (0,1), (1,1), (0,0).

Когда меня спросили об этом, я столкнулся с покерным лицом, мне ничего не пришло в голову.Думаю, для этого нужен сильный геометрический фон.

Answer 1

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

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

Создайте новый массив (набор) точек, в котором мы смещаем наши оси, чтобы они центрировались в точке k. То есть если k = (x _k , y _k ), точка (x, y) станет (xx _k , yy _k ). Сортируйте точки в соответствии с отношением x / y и нормой sqrt (x ² + y ² ). Как показывает следующий шаг, не имеет значения, как выполняется такая сортировка, т. Е. Какой является основным критерием, а какой второстепенным.

Мы могли бы искать дополнение каждой точки или, что лучше, просто пройти массив и убедиться, что каждые две соседние точки действительно являются дополнениями. То есть если это решение, то каждые две дополнительные точки в этом новом массиве имеют вид (x, y) и (-x, -y), так как мы перецентрировали наши оси, что означает, что они имеют одинаковое отношение («градиент») ) и норма, и после сортировки должны быть смежными.

Если k недействительно, то есть точка, к которой мы придем в этом обходе, и обнаружим, что ее сосед не имеет правильной / дополнительной формы ==> такого k не существует.

Время =
O(n) для поиска кандидата k +
O(n) для построения нового массива, поскольку каждая новая точка может быть вычислена в O (1) +
O(nlogn) для сортировки +
O(n) для проверочного обхода
= O(nlogn)

Answer 2

Я бы сказал, что вы просто вычисляете центр масс (сначала удалив дубликаты) и проверяете, является ли он вашим k.Вероятно, единственная причина, по которой он будет O(n log n), - это поиск точки в указанном месте.