求能覆盖点集的最小内接圆


给定N个点,再给定一个最小聚集半径R,
求:需要多少个聚集圆(圆半径均为R),才能覆盖所有点?
同时,需要给出每个圆的位置

其最典型的场景应该是在地图上,用于将地图上的商店按位置分成若干个堆

===我的解法:
最简单的解法,遍历N个点,找到距离小于R的点,即纳入一个圆,圆心为其内所有点X、Y坐标的平均值
这个算法,胜在简单,快速。 但是,准确性就不太高了

希望能找到一个准确性高,同时CPU消耗小的算法
已邀请:

超级大笨狼 - 算法应用

赞同来自: LostOsiris


最小聚集半径R,改叫商圈半径,或者无线基站,wifi之类的,接近实际应用。
商圈规划?题目换成补轮胎比较象

以下答复非针对本题目,发散思维
圆心为其内所有点X、Y坐标的“平均值”这不符合实际视野,实际应该用“中位数”,人的眼球总是关注密集,放弃异常,try it。

GeoHash +Trie 字典树组合 做类似功能,比如查找某点附近m个,预处理O(N),查找接近O(m)。
N的大小为全球,“附近”可以是很密集,也可以是西伯利亚。
你题目换成这个就有意思多了,建议July,多出些看起来更象实际应用的例子,稍微转化下就可以。

GeoHash的原理还适合做其他高维度的模糊聚类,可以降维到1,但是模糊。

这些启发很震撼,算法应用,力量强大,绝对超乎想象。

要回复问题请先登录注册

收藏七月在线,一起向大牛进阶

ctrl+D或command+D可以快速收藏哦~