相关疑难解决方法(0)

我有一个维度为d的n个点的S ,我可以根据需要计算所有成对距离.我需要在这个集合中选择k个点,以便它们成对距离的总和是最大的.在其他稍微更多的数学词中,我想要S中的p1,...,pk使得sum(i,j <k)dist(pi,pj)是最大的.

我知道这个问题是关系到这一个(这基本上是我的一样,但对于k = 2),也许到这一个(使用而不是"最近""最远的").

我对此并不太确定,但也许所有可能的解决方案都有其在凸包中的所有点？

任何合理的近似/启发式都可以.

虚拟奖励点#1用于解决方案,该解决方案适用于给出四个点中的分数的任何函数(其中一个可以是平方距离之和的平方根).

如果解决方案很容易在python + numpy/scipy中实现,那么虚拟奖励点#2.

给定一组有序的2D像素位置(相邻或相邻对角线),形成一条没有重复的完整路径,如何确定多边形的最大线性尺寸,其周长是该像素集？(其中GLD是集合中任何一对点的最大线性距离)

就我的目的而言,明显的O(n ^ 2)解决方案对于数千个点的数字可能不够快.是否有良好的启发式或查找方法使时间复杂度更接近O(n)或O(log(n))？

比方说,我有一个数组CGPoints(包裹着NSValues).我怎样才能得到彼此距离最远的两个点.我的意思是这两点之间的距离最大？我可以检查每两个点,但这看起来效率不高.有没有更好的方法呢？

感谢帮助!