在平面上给定U个n点的集合，您可以在恒定时间内计算任意一对点之间的距离。选择一个称为C的U的子集，以使C恰好具有k个点，并且对于给定的k，C中最远的2个点之间的距离应尽可能小。1 <k <= n
除了显而易见的n-choose-k解决方案，最快的方法是什么？
一个解决方案在“ 找到具有最小直径的k个点和相关问题”（Aggarwal，1991）中显示。其中描述的算法具有运行时间：O(k^2.5 n log k + n log n)
O(k^2.5 n log k + n log n)
对于那些无法获得论文的人：问题称为 k直径 ，定义为
找出一组具有最小直径的 k 点。集合的 直径 是集合中任何点之间的最大距离。
我不能真正地 概述 所提出的算法，但是它包括计算点的 （3k-3）阶Voronoi图 ，然后解决每个 O（kn） Voronoi集的问题（通过计算最大独立集）在一些二部图中）…我想我想说的是，它是非常重要的，并且远远超出了采访和本网站的范围:-)
