从给定的 n 个点中选择最近的 k 个点 [英] Choose the closest k points from given n points

问题描述

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

You are given a set U of n points on the plane and you can compute distance between any pair of points in constant time. Choose a subset of U called C such that C has exactly k points in it and the distance between the farthest 2 points in C is as small as possible for given k. 1 < k <= n

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

What's the fastest way to do this besides the obvious n-choose-k solution?

推荐答案

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

A solution is shown in Finding k points with minimum diameter and related problems - Aggarwal, 1991. The algorithm described therein has running time: O(k^2.5 n log k + n log n)

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

For those who have no access to the paper: the problem is called k-diameter and definied as

找到一组具有最小直径的 k 个点.集合的直径是集合中任意点之间的最大距离.

Find a set of k points with minimum diameter. The diameter of a set is the maximum distance between any points of the set.

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

I cannot really give an overview over the presented algorithm, but it includes computing the (3k - 3)th order Voronoi diagram of the points, and then solve the problem for each of the O(kn) Voronoi sets (by computing maximum independent sets in some bipartite graphs)... I guess that I am trying to say is, that it is highly non-trivial, and far beyond both an interview and this site :-)

这篇关于从给定的 n 个点中选择最近的 k 个点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！