第232页 | 算法技术手册 | 阅读 ‧ 电子书库

同步阅读进度,多语言翻译,过滤屏幕蓝光,评论分享,更多完整功能,更好读书体验,试试 阅读 ‧ 电子书库

范围查询

有一个矩形区域R[xlow,ylow,xhigh,yhigh],以及一个点集P,请问P中哪些点是在矩形区域R中的呢?穷举算法会检查所有的点,花费的时间为O(n),我们能够做得更好么?使用kd树,我们将会阐述如何高效地解决在笛卡儿平面上的范围查询。

r是在R中的点的个数。当然,当点是d维时,这个问题就成了d维范围查询,能够在O(n1-1/d+r)的时间内得到解,如图9-24所示。

图 9-24 范围查询详解
输入/输出

输入

一个d维的点集P和一个d维的正方体。

输出

在这个区域内的所有点,不要求按顺序输出。

假设

查询的范围维度是数据的维度保持一致。

请支持我们,让我们可以支付服务器费用。
使用微信支付打赏


上一页 · 目录下一页


下载 · 书页 · 阅读 ‧ 电子书库