Выберем наиболее близкие k точек из заданных n точек

Вам предоставляется множество U из n точек на плоскости, и вы можете вычислить расстояние между любой парой точек в постоянное время. Выберите подмножество U, называемое C, такое, что C имеет ровно k точек в нем, а расстояние между самыми дальними 2 точками в C как можно меньше для данного k. 1 < k <= n

Какой самый быстрый способ сделать это, помимо очевидного решения n-select-k?

Ответ 1

Решение показано в Поиск k точек с минимальным диаметром и смежными проблемами - Aggarwal, 1991. Алгоритм, описанный в нем, имеет время работы: O(k^2.5 n log k + n log n)

Для тех, у кого нет доступа к газете: проблема называется k-диаметром и определяется как

Найдите набор из k точек с минимальным диаметром. Диаметр множества - это максимальное расстояние между любыми точками множества.

Я не могу дать обзор представленного алгоритма, но он включает в себя вычисление диаграммы (3k - 3) -го порядка Вороного точек, а затем решение проблемы для каждого из множеств O (kn) Voronoi (путем вычисления максимальные независимые множества в некоторых двудольных графах...) Я предполагаю, что я пытаюсь сказать, что это очень нетривиально и далеко за пределами интервью и этого сайта:-)

Ответ 2

Поскольку это вопрос интервью, вот мой пример решения. (Как указывает dcn ниже, это не гарантирует возврата оптимального решения, хотя оно все равно должно быть приличной эвристикой. Хороший улов, dcn!)

Создайте набор S _p с одной точкой P.
Вычислить расстояние между каждой точкой в S _p и каждой точкой вне ее, затем добавить точку с наименьшим максимальным расстоянием до S _p.
Повторите 2. до тех пор, пока S _p не будет иметь k точек.
Повторяйте 1-3, используя каждую точку один раз в качестве начального P. Возьмите S _p, который имеет наименьшее максимальное расстояние.

В S _p есть O (k) точки, а O (n) - вне ее, поэтому найти точку с наименьшим максимальным расстоянием O (nk). Повторяем это k раз, затем повторяем всю процедуру n раз, для общей сложности O (n ² k ²).

Мы можем улучшить это путем кеширования максимального расстояния между любой точкой в S _p и каждой точкой вне S _p. Если maxDistanceFromPointInS[pointOutsideS] является, скажем, хэш-таблицей O (1), содержащей текущее максимальное расстояние между каждой точкой pointOutsideS и некоторой точкой внутри S _p, то каждый раз, когда мы добавляем новую точку newPoint, положим maxDistanceFromPointInS[p] = Max(maxDistanceFromPointInS[p], distance(newPoint, p)) для всех точек p вне S _p. Тогда нахождение наименьшего максимального расстояния равно O (n), добавив точку к S _p - O (n). Повторение этого k раз дает O ((n + n) k) = O (nk). Наконец, мы повторяем всю процедуру n раз, для общей сложности O (n ² k).

Мы могли бы улучшить поиск наименьшего максимального расстояния до O (1) с помощью кучи, но это не изменило бы общую сложность.

Кстати, потребовалось час, чтобы написать все это - я бы не смог это сделать в интервью.

Ответ 3

Это все еще запутанная идея, ~~Я не уверен, работает ли она на самом деле.~~ Это не работает. Оставив неправильный ответ здесь для потомков.

For each point in U
    make a list of the distance to each point in U
    sort the list
    add largest distance to a max-heap.
while any of the lists have more than k elements
    remove max of heap twice
    remove corresponding elements from the two lists they came from
    add the two newly exposed largest elements from those two lists to the heap
Any of the lists left with k elements will list the elements in C

В принципе, найдите две точки, которые в настоящее время выглядят так, как будто они оба находятся в подмножестве вместе и имеют наибольшее попарное расстояние, а затем исключают, что оба они находятся в подмножестве вместе. Повторяйте, пока вы не останетесь только с одним возможным способом формирования подмножества k-размера.

Это должна быть временная сложность O ((n ^ 2) log (n)) и пространственная сложность O (n ^ 2).

Ответ 4

Его можно сделать в детерминированном полиномиальном времени.

Но я не понимаю их алгоритм. Кажется, что круги, которые они выбирают, всегда являются одной из входных точек. Может кто-то пролить свет на это или объяснить аккуратно, что они делают (просто раздел 2 будет достаточным)?

Ответ 5

Реальная проблема, которая была задана, кажется сложной. Если точки не были в плоскости и имели произвольные расстояния, это было бы NP-жестким путем уменьшения от k-clique (взять произвольный невзвешенный график и добавить края бесконечности длины для отсутствующих краев, а ребра длины 1 для существующих ребер - клика размера k существует всякий раз, когда "ближайшие точки k" имеют максимальное взаимное расстояние 1, а не бесконечность). Однако, поскольку точки ограничены тем, что они находятся в плоскости, так что такие метки расстояния запрещены, возможно, что может быть решение. По крайней мере, кажется, это подходит к близкому приближению.

Если ваше интервью означало "круг наименьшего диаметра, охватывающий k точек", то следующий алгоритм может быть самым быстрым правильным алгоритмом, который вы могли бы придумать сами в интервью:

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

По существу, это цикл с четырьмя вложенными циклами, поэтому время работы равно O (n ^ 4).

Ответ 6

Это должно быть хорошим приближенным решением, если у вас слишком много выбросов

p = mean center (average x, y) of U
M = U sorted by distance to p
C = M[0:k]