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

问题描述

正在给飞机上的一组n个点的U和可以计算在固定时间内的任何一对点之间的距离。选择的U子集称为C，以使得C中有k个点和C中的最远的2点之间的距离是尽可能小的给定ķ。 1＆LT; K＆LT; = 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

什么是做到这一点，除了明显的正选-K的解决方案以最快的方式？

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

推荐答案

一个解决方案，显示在<一个href="http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WH3-4CRJ34X-W&_user=10&_coverDate=03/31/1991&_rdoc=1&_fmt=high&_orig=gateway&_origin=gateway&_sort=d&_docanchor=&view=c&_rerunOrigin=scholar.google&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=dbd17c453a3361fe6c94c41b64e39b21&searchtype=a">Finding k个点与最小直径和相关问题 - AGGARWAL，1991年。 其中描述的算法运行时间： O（K ^ 2.5的n log K + N日志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-直径的和definied为

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.

我真的不能给出的概述的超过presented算法，但它包括计算的（3K - 3）之分阶Voronoi图的，并那么解决问题对每个的 O（KN）的沃罗诺伊集（通过计算最大独立集在一些二部图）......我想，我想说的是，这是非常不-trivial，并远远超出了这两个面试，本网站:-)

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屋！