我在 D 维度量空间中有一组 N 个点。我想以这样的方式选择其中的 K 个，即子集中任意两点之间的最小距离最大。
例如，在 3D 欧几里得空间中 N=4 和 K=3，解是具有最长短边的四面体面。
有没有经典的方法来实现这一目标？它可以在多项式时间内精确求解吗？
我已经尽可能多地搜索了，但我还没有弄清楚如何调用这个问题。
在我的情况下，通常 N=50、K=10 和 D=300。
澄清：
蛮力方法是尝试 N 中 K 点的每种组合，并确定每个子集中最接近的对。解决方案由产生最长对的子集给出。
完成了简单的方法，一个 O(K^2) 过程，要重复 N！/K!(NK)! 次。
哼，10^2 50！/ 10！40！= 1027227817000
我认为您可能会发现有关单位磁盘图的论文内容丰富但令人沮丧。例如，http://citeseerx.ist.psu.edu/viewdoc/download?doi =10.1.1.84.3113&rep=rep1&type=pdf指出在 NP-complete 中单位圆盘图上的最大独立集问题，即使圆盘表示是已知的。单位圆盘图是通过在平面上放置点并在每对点之间形成最多相距单位距离的链接而得到的图。
所以我认为，如果你能在多项式时间内解决你的问题，你可以在单位磁盘图上针对不同的 K 值运行它，直到找到一个值，在该值处，两个选定点之间的最小距离刚刚超过 1，我认为这将是单位圆盘图上的最大独立集，这将在多项式时间内解决 NP 完全问题。
（正要骑自行车，所以这有点匆忙，但在单位磁盘图上搜索论文至少可能会找到一些有用的搜索词）
这是一个尝试逐个解释它的尝试：
这是将这两个问题联系起来的另一种尝试。
有关最大独立集，请参见http://en.wikipedia.org/wiki/Maximum_independent_set#Finding_maximum_independent_sets。一个决策问题版本是“这个图中是否有 K 个顶点，使得没有两个顶点被一条边连接？” 如果你能解决这个问题，你当然可以通过针对不同的 K 询问这个问题来找到最大的 K 来找到最大的独立集，然后通过在删除了一个或多个节点的图形版本上询问问题来找到 K 个节点。
我在没有证据的情况下声明在单位磁盘图中找到最大独立集是 NP 完全的。另一个参考是http://web.sau.edu/lilliskevinm/wirelessbib/ClarkColbournJohnson.pdf。
您的问题的决策版本是“是否存在 K 点，任意两点之间的距离至少为 D？” 同样，如果您可以在多项式时间内解决原始问题，则可以在多项式时间内解决此问题-一直玩直到找到给出答案的最大 D 是，然后删除点并看看会发生什么。
当两点之间的距离小于等于 1 时，单位圆盘图恰好有一条边。因此，如果您可以解决原始问题的决策版本，则只需设置 D = 1 并解决您的问题，您就可以解决单位圆盘图问题的决策版本。
所以我想我已经构建了一系列链接，表明如果你可以解决你的问题，你可以通过将它变成你的问题来解决一个 NP 完全问题，这让我认为你的问题很难。