这是一个创建于 5195 天前的主题，其中的信息可能已经有所发展或是发生改变。
问题背景：地球上有很多形形色色的点，而这些所有的点也近似上构成了这个地球集R
现在的智能手机都具备定位功能 (通过GPS,蜂窝，基站等)，获取经纬度，于是可以支持周边搜索。
而现在很多实际周边搜索都是基于这个地球集R计算的，而存在的问题是：每搜索一次，都要从地球集R出发，找出周边的点，这样，当搜索比较频繁时，不属于周边的那些点都会被重复计算，带来了不必要的查询冗余，而且效率不是很高。
如果可以把这个地球集，提前按区域切分成若干个相同的面积，每一块贴上范围索引，映射成字典。
这样在每次搜索的时候，就可以直接去搜索这个范围索引所在的集合，找到了对应的范围索引，就找到了对应的区域块，也即是这个点的周边区域。
现在的问题是：
对于这么一个庞大的地球集R，如何选择切分形状（面积提前指定，比方100平方公里），才能保证：
1.每一个点都会有象跟它对应
2.切分的区域之间交集最小，以避免数据重复查询。（可能会存在一对多，也就是一个点，被切到周边的多个区域里去了）
现在的智能手机都具备定位功能 (通过GPS,蜂窝，基站等)，获取经纬度，于是可以支持周边搜索。
而现在很多实际周边搜索都是基于这个地球集R计算的，而存在的问题是：每搜索一次，都要从地球集R出发，找出周边的点，这样，当搜索比较频繁时，不属于周边的那些点都会被重复计算，带来了不必要的查询冗余，而且效率不是很高。
如果可以把这个地球集，提前按区域切分成若干个相同的面积，每一块贴上范围索引，映射成字典。
这样在每次搜索的时候，就可以直接去搜索这个范围索引所在的集合，找到了对应的范围索引，就找到了对应的区域块，也即是这个点的周边区域。
现在的问题是：
对于这么一个庞大的地球集R，如何选择切分形状（面积提前指定，比方100平方公里），才能保证：
1.每一个点都会有象跟它对应
2.切分的区域之间交集最小，以避免数据重复查询。（可能会存在一对多，也就是一个点，被切到周边的多个区域里去了）
Select Language