首页 > 试题广场 >

不难理解,kd-树中节点v所对应的矩形区域即便与查询范围R相

[问答题]
不难理解,kd-树中节点v所对应的矩形区域即便与查询范围R相交,其中所含的输入点也与见得会落在R之内。比如在极端的情况下,v中可能包含大量的输入点,但却没有一个落在R之内。当然,kdSearch()(算法8.2)
在这类情况下所做的递归,都是不必进行的。克服这一缺陷的一种简明方法,如图x8.7所示:在依然保持各边平行于坐标轴,同时所包含输入点子集不变的前提下,尽可能地收缩各矩形区域。其效果等同于,将原矩形替换为依然覆盖其中所有输入点的最小矩形——即所谓的包围盒(bounding-box)。其实,在如图 8.41 所示的实例中,正因为采用了这一技巧,才得以在节点{F, H}处,有效地避免了一次无意义的递归。
试按照以上构思,在算法8.1的基础上,改进kd-树的构造算法。

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