主页
程序 数学 设计 杂谈
主页

Contents

计算几何课程

   5225 words   11 minutes 

07几何范围查找(Geometric Range Search)

计算几何-笔记目录

在第六章中主要讨论的是点定位问题，及给定平面的刨分和一个点，确定点所在位置。本章则相当于其反向问题版本，给定一个矩形，确定哪些点被包含在这个矩形当中。本章业主要以在线算法为主，即给定点是预处理好的，而输入查询则是随机不可预期的。

  • Range Query
    • 介绍范围查询在线算法概念，并以一维范围查询来初探该类问题。在一维情况下很简单，但是不容易直接推广到二维情况下。
  • BBST
    • 介绍后面要用到的一种特殊BBST，并对其进行分析。使用该BBST也可以快速定位一维范围查询，虽然该结构复杂但可以推广到二维。
  • kd-tree
    • 介绍引入kd-Tree概念。主要讲解了kd-Tree的构造方式。
  • kd-Tree: Algorithm
    • 介绍kd-Tree的查询计算方式，并举出例子来说明。
  • kd-Tree: Performance
    • 对二维kd-Tree进行性能分析。主要为构造耗时，存储消耗，查询时间等分析。也说明kd-Tree可以推广到任意维度都可行。
  • Range Tree: Structure
    • 介绍Range Tree，讲解其结构，说明RangeTree的由来和原因。
  • Range Tree: Query
    • 介绍在Range Tree上来进行查询的算法过程。
  • Range Tree: Performance
    • 本节主要对Range Tree进行性能分析。分析其存储，预处理以及查询效率。存储空间大小在$O(nlogn)$范围，预处理时间花费在$O(nlogn)$，而查询需要$O(r+log^2n)$的时间。
  • Range Tree: Optimization
    • 本届主要对Range Tree进行优化。目标是为了使得2维查询变成$O(logn)$时间量级。思路是最后Y查询的时候，可以发现不同条带之间，上下两个横街轴是共同的。

范围查找介绍

问题
几何范围查找，其实相当于点定位得对偶问题。这里则是先给出一堆0维元素，即一堆点。然后给出一个几何范围。现在来问，哪些点被包含在这个范围里面。

一维情况

如图，即给定线段上一系列点$P=\set{p_1,\cdots,p_2}$。然后给定一个区间$I=(x_1,x_2]$这里有两个问题：

  • Counting：报告有多少个点被$I$覆盖。
  • Reporting：报告有哪些点被$I$覆盖。

这里有个直接最简单的想法，就是将所有点预处理成有序向量。然后施加二分查找即可。显然时间复杂度是$O(logn)$，而对于枚举问题，目标输出集合大小是不可避免的，假设输出大小为$r$，复杂度为$O(r+logn)$

但是很可惜的是这样一种方式，并不能推广到2维。

一维BBST

所以这里为了能在高维中也有效查找，所以要建立一个高效数据结构来完成。前面可以看到是一个有序向量，而这样一个结构就可以进一步设计为一个BBST结构。

即每一个节点都存放着这个节点左子树中最大的数值，所以这样一个BBST有这么一个简单性质，对任意一个节点来说，即左子树的节点值都小于这个节点上的数，右子树的节点值都大于这节点值。

现在来看这样一个结构的查找问题，也是分成两部分，Counting和Reporting。对于Reporting来说，很简单，给定$I=(x_1,x_2]$从根查找到对应的节点后，调用后继遍历即可。时间复杂度任然为$O(r+logn)$

但是对于Counting问题，则需要快速的计数操作。这里需要注意到$x_1,x_2$两条查找路径。对于这两个查找路径有一个最小公共祖先LCA，即在这个LCA节点上时，发生了拐弯，$x_1$向左，$x_2$向右。这时候注意来两个数值之间的个数，就是这两个路径之间夹住的字数的大小。具体可以描述为，对于$x_1$路径，每次向左前行时，把右子树的数量完整报告出来。对于$x_2$路径，则每次向右前行时，把左子树的数量完整报告出来。这样可以简单看出来对于Counting来说其复杂度任然是$O(logn)$量级的。

而对于这样一个结构，其生成的时间复杂度不会超过$O(nlogn)$，进行一个排序然后自底向上构造就可以了。

KD-Tree

上面这样一个树形结构，看上去可能很复杂。但是其是可以推广到更高维度的。

思路
沿承上面数组的划分思想。对于2维来说，递归的将平面划分成一系列区域。然后组成一棵树以供查询。

KD树即基于这样一个思路下构造树的方式。KD树即K Dimension Tree。在2维情况下即2维树。对于2维平面的划分，给定一个点集合$P$，可以用如下过程来描述：

  • 如果$P$只有一个点，平凡情况，生成一个叶子节点。
  • 否则对$P$进行一个均匀划分，划分方式应按照维度逐步进行，对2维来说即x方向与y方向交替划分。
    • 当层高为奇数时：按照x方向划分，即取所有点在x方向上的中位数点为分界线，构造左右两个子集。
    • 当层高为偶数时：按照y方向划分，即取所有点在y方向上的中位数点为分界线，构造左右两个子集。

其划分流程示意图如下：

大体来说，一开始按照x方向，找到中位数，划分层两部分。然后第二层按照y方向划分成两部分。依次进行直到所有区域都只包含一个节点，由此生成叶子节点。

可以看到这样一棵树有如下特性：

  • 对于这棵树无论叶子节点，还是中间节点都对应一个长方形子区域。
  • 无论是哪一层，所有子区域的并集都会覆盖整个平面，同时这些子区域没有任何重叠。即每一层都是一个平面的划分。
  • 同时每一个中间节点，其所代表的子区域都会被其子树所代表的子区域划分。

现在来关注在这样一个结构上做几何范围查找的问题。即给定一个区域，求有多少点被覆盖。

其流程如图中所示，大致来说思路就是当抵达一个节点时，我们不断判断其左右子树是否被包含在范围$R$中。如果包含那么只要将子树中的所有节点报告出来就可以。如果对应子区域与$R$相交，那么要进一步搜索子树。如果子区域完全在$R$之外，那么完全不需要处理，跳过就可以。

同时需要注意的是，如果最后搜索到了叶子节点。那么这个时候就要判断这个区域中的点是否在范围$R$中。

非常需要注意的是，这个只是一个理论的介绍。在实际运用的时候，有巨大的优化空间。例如如下就是一种优化方式：

这个思路就是，我们前面采用完全划分的想法。这个边界过宽，导致搜索不能完全终止。实际上对于中间节点来说，其子树的节点都未必会将区域填满，简单来说，就是边界可以瘦身。

所以这里不再是用整个子区域划分，而是用子集的点的一个最小包围盒来取代子树用来判定的区域。经过这样的划分，可以看到，对于区域判定来说，有些分支可以提前终止。

算法复杂度分析

显然构造过程中是将点集合均匀划分成两部分，所以构造时间为$O(nlogn)$。

现在来看其报告查询时间。如图：

对于一个范围查询来说，这里只有一种情况需要递归，即那些与边界相交的区域。对于那些完全落在区域里面的子树，会直接报告，对于完全落在区域外的子树则被剪枝。

现在问题就是分析每一层，与边界区域相交多少次。这个直接逐层分析会很难分析。这里用到的方法，或者说思路。就是每两层两层的来分析。即从一个区域，与下面四个区域的关系入手，如图。

但是这样依然很难统计，这里就改为分析一条边即可。最后该边相交的个数乘以4即整个正方形所要花费的时间复杂度。这里可以显然看出，对于这样一条直线来说，此层一定只有2个子区域与其相交。而这两个区域就是要递归查找的区域。所以有：

$$Q(n)=2+2*Q(n/4)=\sum_{i=1}^{log_4n}2^i+2^{log_4n}Q(1)=2\sqrt{n}-2+\sqrt{n}Q(1)$$

前面都是以2维为例。但是前面也说了，其可以扩张到任意K维。也是因为如此，才称之为KD-Tree。那么对于更高维来说，只要依次按照维度轮变即可。对于这样一个K维度的KD-Tree，可以的到其范围查询时间复杂度为$n^{(1-1/d)}$。可以看到当维度足够高的时候，可以发现，这个时候查找效果，基本就是$n$即退化到最早的蛮力算法。

Range Tree

上面可以看到对于KD-Tree来说，其时间复杂度还是略高的。这里按照原来的思路继续往前走，还可以得到更好的算法。

思路
这个思路来源于，对于任意维度的正交范围查询。都可以分解为对应维度上的范围查询。然后在把所有维度上的结果，来进行一个组合。

对于2维来说，就可以分解维先对x维度进行一波查询，然后再对y维度进行一波查询。但是这样的方式显然存在着最坏情况。例如在x维度都很密集聚集在一起。但是y维度上点特别稀疏，基本只有1个。这样先按照x基本会报告所有点，然后y维度上只报告出1个。但是突破这种问题，就是算法要做的事情。

一个Range Tree结构可以如下图表示。

  • 首先x方向构建一个如前所述的BBST。
  • 但是在这棵BBST中每个节点不再是一个点，而是对应着一棵BBST。因为x方向中中间节点实际上表示着一个在x轴方向上划分的点即。所以可以通过再进一步在y轴上划分成一棵新的BBST来处理问题。

以这样的方式构建了一个多层搜索树。这个查找过程可以通过下图表示：

首先在x方向进行一个搜索，这个搜索会跟1维的时候一样，从某一个节点开始出现分叉。而在这个分叉之间的那些区域就是我们要进一步搜索的区域。这相当于左图中一些列垂直的Slab。而树中每一个节点对应一个Slab。而每一个节点会给出一个y方向的子树。注意的是，这些子树并不是直接挂在这些节点上，而是由其左右子树拼装构成的一个BBST树。然后再每棵子树上进行y方向的子树查询。

空间复杂度

现在来看这个多层搜索树空间复杂度。这个数据结构，有多层树。对于x树来说，非常简明，其空间复杂度就是$O(n)$。现在来看y树，根据前面所见，这个树数量可能多达$n$个。同时每一个点可能存在每一棵y树中，这样看每一棵y树可能多达$n$个节点，进而空间复杂度为$O(n^2)$。

但是可以考虑子区域覆盖状况。对于y树来说，都是挂在x树节点上的。如果一个点在子结点中，那么其必然也会存放在父节点中。所以一个节点最多存放$O(logn)$次。

其实还有一个更直接的思路，对于每一层x树来说，其y树都应该包含所有节点，也就是说，这一层y树是一个所有点的划分。也就是每一个点，只可能在每一层存放1次。x树树高为$logn$，显然所有节点总数即$nlogn$。

构造复杂度

构造时间复杂度是$O(nlogn)$，还是非常高效的，对于新增的y树并没有加大构造的时间复杂度。

其实这个算法可以这样来构造，就是自底向上的来构造。先把所有点按x轴来排序花费$O(nlogn)$时间。然后这时候可以注意到此时所有叶子节点只有一个点，同时也表示这个y树只有一个节点。

现在自底向上的构造。即每两个叶子结点开始，向上构造一个x节点，同时把两个子树合并成父节点的子树。这一步类似于MergeSort。显而易见，这一步构造时间复杂度即两个子树的大小。所以自低向上的Merge也只会开销$O(nlogn)$时间，并没有改边时间复杂度。

查询复杂度

最后这样一个查找效率可以达到$O(r+log^2n)$的效率。这是因为在第一层会花费$logn$时间找出$logn$个树，每个y树都可能是一个多达$n$量级的查找，所以就是$log^2n$的查找效率。这个界是紧的。

对于$d$维空间来说，其查找效率也可以达到$O(r+log^dn)$的量级，而其空间复杂度则为$O(nlog^{d-1}n)$。

优化

上面看到对于Range Tree查询会需要$O(r+log^2n)$的时间复杂度。这里有一个优化方案可以应用到最后一层中去，进而优化查询效率可以使其降低到$O(logn)$复杂度。

思路
可以看到之前的算法，对于y方向的查找，同一个y方向值，在每一个ytree上重复进行了$O(logn)$次。所以如果作用一个方向值，可以得到其他所有树上的关联数值，就可以剩下重复查询时间。而这种y轴数值关联，就是通过一个全局的y方向顺序表来实现。

具体来说，就是对于每一个节点，其有一个y树，这个数可以被一个有序向量来表示。如果从父节点跳转到子节点的过程中，能通过父节点的y方向有向序列来快速得到子节点的y位置。可以剩下大量的y轴查询时间。其整个结构就如下图：

  • 首先把y树改成一个有序向量。
  • 然后从x树来说，对于节点$V$来说有一个y方向有序向量$y-list$，会切分成$V_L,V_R$。此时$V_L,V_R$也有其对应的y方向有序向量$y_L-list,y_R-list$。
  • 这时候可以建立一个从$V$到$V_L,V_R$有向序列的指向关联。这样一个指向建立方式很简单，即指向子序列中那个不大于它的元素。
  • 这样可以发现对于$y-list$的一个搜索，可以快速关联到$y_L-list,y_R-list$中去。得到其搜索结果。

这种技术称之为Fractional Cascading。其实可以认为就是建立了一个y方向全局顺序表，然后按照x树的左右行进，逐步把这个全局列表逐步细分。当用$y_1,y_2$检索全局$y-list$的时候，就可以通过这个x树分别映射到每个子树区间上去。进而把查找时间变为一次全局y方向的查找。这种查找时间复杂度为$O(1)$。

所以这种技术可以使得2维RangeTree的时间复杂度降为$O(logn)$。而对于高维来说，可以发现，其只能作用在最后一层即，之恶能剩下最后一层的查找时间。可以的到对于$d$维空间来说，其查找效率为$O(r+log^{d-1}n)$

Updated on 2023-08-26
Back | Home