从给定的n个点中选择最接近的k点

Question

您将在平面上获得一组U个n点,并且可以在恒定时间内计算任意一对点之间的距离.选择一个名为C的U的子集,使得C中恰好有k个点,并且C中最远的2个点之间的距离对于给定的k尽可能小.1 <k <= n

除了明显的n-choose-k解决方案之外,最快的方法是什么？

Answer 1

解决方案显示在寻找具有最小直径和相关问题的k点 - Aggarwal,1991.其中描述的算法具有运行时间:O(k^2.5 n log k + n log n)

对于那些无法访问论文的人:这个问题被称为k-diameter,并被定义为

找到一组最小直径的k点.一组的直径是该组的任何点之间的最大距离.

我不能真正概述所提出的算法,但它包括计算点的(3k - 3)阶Voronoi图,然后解决每个O(kn) Voronoi集的问题(通过计算最大独立集)在一些二分图中)...我想我想说的是,这是非常重要的,远远超出了采访和这个网站:-)

Answer 2

由于这是一个采访问题,这里是我的解决方案. (正如dcn指出的那样,这不能保证返回最佳解决方案,尽管它应该仍然是一个不错的启发式.好的捕获,直接!)

1. 创建一个单点P 的集合S _p.
2. 计算S _p中每个点与其外部的每个点之间的距离,然后将具有最小最大距离的点添加到S _p.
3. 重复2.直到S _p有k个点.
4. 使用每个点作为初始P重复1-3.获取具有最小最大距离的S _p.

在S _p中有O(k)个点,在它外面有O(n)个点,因此找到具有最小最大距离的点是O(nk).我们重复这个k次,然后重复整个过程n次,总体复杂度为O(n ² k ²).

我们可以通过缓存之间的最大距离改进这一点任何处于S点_p和S以外的每个点_p.maxDistanceFromPointInS[pointOutsideS]例如,如果是包含每个点pointOutsideS与S _p内某个点之间的当前最大距离的O(1)哈希表,则每次我们添加新点时newPoint,我们设置S _p之外的maxDistanceFromPointInS[p] = Max(maxDistanceFromPointInS[p], distance(newPoint, p))所有点.然后找到最小的最大距离是O(n),向S _p添加一个点是O(n).重复该k次给出O((n + n)k)= O(nk).最后,我们重复整个过程n次,总体复杂度为O(n ² k). p

我们可以使用堆来改善找到与O(1)的最小最大距离,但这不会改变整体复杂性.

顺便说一下,花了一个小时写完这一切 - 我无法在面试中做到这一点.