(稀疏包分布) 考虑计算平面上点集的凸包问题，但这些..._

(稀疏包分布) 考虑计算平面上点集的凸包问题，但这些点是根据某已知的随机分布取得的。有时，从这样一种分布中取得的n个点凸包的期望规模为O(n^1-)，其中ε为某个大于0的常数。称这样的分布为稀疏包分布。稀疏包分布包括以下几种:

点是均匀地从一个单位半径的圆面中取得的，凸包的期望规模为 $\Theta$ (n^l/3)。
点是均匀地从一个具有k条边的凸多边形内部取得的(k为任意常数)。凸包的期望规模为 $\Theta$ (lgn)。
点是根据二维正态分布取得的。凸包的期望规模为 $\Theta$ ( $\sqrt{lgn}$ )。

a.已知两个分别有n1和n2个顶点的凸多边形，说明如何在O(n1 + n2 )时间内计算出全部n1 +n2个点的凸包(多边形可以重叠)。
b.证明:对于根据稀疏包分布独立取得的一组n个点，其凸包可以在O(n)的期望时间内计算出来。(提示: 采用递归方法分别求出前n/2个点和后n/2个点的凸包，然后再对结果进行合并。)

(稀疏包分布) 考虑计算平面上点集的凸包问题，但这些...

问题信息

热门推荐

相关试题