Page 51问题定义与暴力法物理问题给定N个轴对齐矩形边与坐标轴平行找出所有相交的矩形对。暴力解法检查所有矩形对N²次比较判断它们是否重叠。非退化假设所有x和y坐标互不相同。这个假设与线段相交那一节相同目的是避免讨论边界重合的复杂情况让你先理解算法骨架。Page 52应用场景VLSI 设计规则检查物理映射在芯片版图VLSI layout中不同导线wires位于不同金属层但它们之间必须保持一定间距spacing避免短路或信号干扰。具体操作矩形相交检测是设计规则检查DRC的核心。你需要找出所有“本该分开但实际重叠”的矩形对或是“间距不足”的矩形对。因此rectangle intersection算法在 EDA电子设计自动化工具中是基础组件。你所在的领域DFT虽然更侧重测试但版图验证是芯片设计流程中紧邻 DFT 的前一站二者使用的几何算法高度重叠。Page 53为什么不能用平方级算法摩尔定律的推导物理原因如果使用平方级算法当芯片规模翻倍N → 2N时运行时间变为原来的 4 倍。即使计算机速度也翻倍2x运行时间依然变为原来的 2 倍。这意味着随着工艺进步检查时间会持续增加无法跟上设计规模的增长。结论必须要用线性对数N log N的算法才能保证运行时间与芯片规模同步增长。这正是扫描线算法的物理动机。Page 54扫描线算法核心归约这是整节最重要的页面。它的物理动作与之前处理线段相交的扫描线完全一致但数据结构从“BST 存y坐标”升级为“区间搜索树存y区间”。物理过程从左到右移动扫描线。扫描线经过的事件是矩形的左边界和右边界。数据结构维护一棵区间搜索树Interval Search Tree存储当前与扫描线相交的所有矩形在y轴上的投影区间[y_low, y_high]。遇到矩形左边界时用该矩形的y区间[y_low, y_high]在区间搜索树中做一次区间相交查询。所有命中的区间都对应一个与当前矩形相交的活跃矩形输出这些矩形对。将当前矩形的y区间插入到区间搜索树中因为它从此刻开始变得“活跃”。遇到矩形右边界时从区间搜索树中删除该矩形的y区间因为它从此失效。物理正确性当两个矩形在二维平面上相交时在扫描线从左向右移动的过程中必定存在一个x位置使得它们同时与扫描线相交并且它们的y区间重叠。此时左侧矩形的“插入事件”发生在右侧矩形的“插入事件”之前或同时在插入右侧矩形时进行区间查询就能捕捉到所有重叠。rectangle intersection的检测方法是结合sweep line和interval search treePage 55复杂度分析1. 预备阶段无论如何都必须做对2N个矩形端点左边界和右边界按x坐标排序准备扫描线事件队列。成本O(N log N)。2. 扫描线维护阶段无论如何都必须做扫描线从左向右移动每个矩形会产生一次插入遇到左边界和一次删除遇到右边界。区间搜索树Interval Search Tree的插入和删除操作的时间复杂度为O(log N)。因此动态维护整棵树的总成本为N * O(log N) N * O(log N) O(N log N)。3. 相交查询与输出阶段查询搜索起始点当一个矩形的左边界触发相交查询时区间搜索树需要找到第一个与目标区间相交的活跃矩形。这一步需要从根节点开始下降成本为O(log N)。枚举输出找到所有匹配项找到第一个匹配的区间后通过迭代器或中序遍历的后继指针访问下一个匹配项在标准实现中每次移动的均摊成本为O(1)。因此输出所有R个相交对的实际成本为O(R)。注意PPT 中写的O(R log N)是一个保守的、简化的数学上界它假设每输出一个相交对都重新进行一次独立的树搜索。但在迭代器模式下物理成本是线性的O(R)。最终总复杂度修正版O(N log N) O(R)如果您需要保留 PPT 的保守写法应表述为预处理与动态维护O(N log N)输出结果O(R)平摊常数时间总计O(N log N R)Page 56总结表这张表把整讲几何搜索的四个算法放在一起对比物理上揭示了一条归约Reduction链条问题解法核心归约1D 范围查找BST二分查找 剪枝遍历2D 正交线段交点扫描线归约为 1D 范围查找2D 正交范围查找点kd-tree递归空间二分1D 区间相交区间搜索树BST 子树max剪枝2D 正交矩形交点扫描线 区间搜索树归约为 1D 区间相交物理结论扫描线的通用策略是“把 2D 问题沿时间轴展开变成 1D 动态维护问题”。kd-tree的通用策略是“把 2D 空间递归切分在空间上进行二分”。