首页 > 试题广场 >

(凸层) 已知平面上的点集Q,我们用归纳法来定义Q的...

[问答题]
(凸层)  已知平面上的点集Q,我们用归纳法来定义Q的凸层(convexlayer)。Q的第一凸层是由Q中属于CH(Q)顶点的那些点组成。对i>1,定义Q;由把Q中所有在凸层1，2，...，i一1中的点去除后所剩余的点构成。  如果Qi≠0,  那么Q的第i凸层为CH(Q);否则，第i凸层无定义。
a.写出一个运行时间为O(n2 )的算法，以找出n个点所组成的集合的各凸层。
b.证明:在对n个实数进行排序所需时间为(nlg n)的任何计算模型上，计算n个点的凸层需要(n lg n)时间。
查看答案及解析
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

上传者：小小
难度：
0条回答 96浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号