优先查找树在计算流体力学中的应用：高效截窗查询

"优先查找树-计算流体力学与传热学 陶文全" 优先查找树（Priority Search Tree，PST）是一种特定的几何数据结构，主要应用于计算几何领域，特别是在处理平面点集和线段的查询问题时，提供高效的性能。在计算流体力学与传热学中，这种数据结构可能用于优化处理与物理模型相关的几何信息，例如在模拟中快速识别与特定查询区域相交的对象。 第10章中提到的定理10.5指出，对于平面上的一组水平线段S，我们可以在O(log2n + k)的时间复杂度内找到与任意垂直线段相交的所有线段，其中k是实际报告出来的线段数。为了实现这个效率，需要一个占用O(nlogn)空间的数据结构，该结构可以在O(nlogn)时间内构建。这个定理结合引理10.1，可以解决与坐标轴平行的线段的截窗问题。 推论10.6进一步扩展了这个概念，指出对于一组与坐标轴平行的线段S，我们同样能在O(log2n + k)的时间内报告出与任一平行矩形截窗相交的所有线段。同样，这也需要O(nlogn)的空间，并且在相同的时间复杂度内构建。 10.2节引入了优先查找树，它改进了第10.1节中基于区域树的数据结构。优先查找树的存储性能提升到了O(n)，这意味着它更节省空间，尤其是处理大量数据时。然而，对于推论10.6中的截窗问题，存储上界仍然是O(nlogn)，因为报告截窗内的所有端点仍然需要区域树。 优先查找树的设计灵感来源于一维情况下的区域查找优化。在处理左侧无限的查询区间时，可以通过从左侧开始遍历有序表直到找到第一个不在区间内的点，从而达到O(1 + k)的查询时间。在二维情况下，优先查找树使用堆数据结构，以便在x坐标位于(-∞ : qx]的点集中，高效地找出y坐标位于[qy : q'y]的点。这样，它能够利用无界一侧的特性来提高查询效率。 计算几何是一门涵盖广泛领域的学科，包括但不限于线段求交、多边形三角剖分、线性规划、正交区域查找、点定位、Voronoi图以及排列和对偶问题等。在这些领域中，优先查找树提供了一种高效的数据结构，尤其适用于处理特定类型的几何查询，如截窗问题，从而在实际应用中发挥重要作用。