压缩四叉树在存储每个对应于细分单元的节点时，我们最终可能会存储大量空节点。通过仅存储其叶子具有有趣数据（即“重要子树”）的子树，可以减少此类稀疏树的大小。同样，我们实际上可以进一步减小尺寸。当我们只考虑重要的子树时，修剪过程可以避免树中路径较长的情况，其中中间节点的度数为二（到一个父节点和一个子节点的链接）。事实证明，我们只需要存储节点 U ... 阅读更多

区域四叉树用于表示二维空间的划分，方法是将区域划分为四个相等的象限、子象限，依此类推，每个叶节点包含对应于特定子区域的数据。树中的每个节点要么与恰好四个子节点相关联，要么没有子节点（叶节点）。遵循此分解策略（即细分子象限，直到并且除非子象限中存在需要进一步细化的有趣数据）的四叉树的高度对空间中有趣区域的空间分布敏感并依赖于空间分布... 阅读更多

点四叉树是二叉树的改编，用于表示二维点数据。点四叉树共享所有四叉树的特征。它通常在比较二维有序数据点方面非常有效，通常在 O(log n) 时间内执行。出于完整性考虑，值得一提的是点四叉树，但 k-d 树作为广义二分搜索的工具超越了它们。点四叉树的构建方式如下。给定要插入的下一个点，我们计算它所在的单元格并将其添加到树中。新点被添加，使得包含它的单元格被... 阅读更多

四叉树是实现的树，用于有效地存储二维空间中点的点数据。在这棵树中，每个节点最多有四个子节点。我们可以从一个二维区域构建一个四叉树，执行以下步骤：当前二维空间被划分为四个盒子。如果一个盒子包含一个或多个点，则构建一个子对象，并在其中存储盒子的二维空间。如果一个盒子不包含任何点，则不要为其构建子节点。对每个子节点执行递归。四叉树在图像压缩中实现，其中每个节点包含... 阅读更多

范围树定义为一种有序树数据结构，用于保存点列表。它允许有效地检索给定范围内的所有点，通常在二维或更高维度中实现。它与 kd 树相同，只是查询时间更快，为 O(logd n + k)，但存储更差，为 O(n logd-1 n)，其中 d 表示空间的维度，n 表示树中的点数，k 表示给定查询检索到的点数。范围树可以与区间树区分开来：而不是... 阅读更多

简介用于模板参数或半边数据结构的 HDS（缩写为 HalfedgeDS）定义为一种以边为中心的的数据结构，能够维护顶点、边和面的关联信息，例如平面图、多面体或其他可定向的二维曲面嵌入在随机维度中。每条边都被分成两个方向相反的半边。每个半边存储一个关联面和一个关联顶点。每个面和每个顶点都存储一个关联半边。半边数据结构的简化变体可以消除其中的一些信息，例如面中的半边指针或面的存储... 阅读更多

在计算几何中，平面直线图，简称 PSLG，（或直线平面图，或平面直线图）定义为在平面上实现平面图嵌入的术语，使得其边映射到直线段。Fáry 定理（1948 年）的陈述是，每个平面图都具有这种嵌入。在计算几何中，PSLG 通常被称为平面细分，假设或断言细分是多边形的。如果没有度数为 1 的顶点，则 PSLG 定义了平面细分为多边形区域，反之亦然。没有... 阅读更多

多元横截面数据（即非时间序列或重复测量）由矩形数据指示，其中每列是一个变量（特征），每行是一个案例或记录。表示矩形数据的第一个过程是将其映射到更高维度的点数据并使用基于点的的数据结构过程，例如网格文件、PR 四叉树、点四叉树和 k-d 树。矩形数据到四维点的过程映射可以通过多种技术执行，例如相对角的 x 和 y 坐标，或一个角的 x 和 y 坐标以及宽度和高度，... 阅读更多

分桶构建散列表为二维数组，而不是一维数组。数组中的每个条目都很大，足以容纳 M 个项目（M 不是数据量。只是一个常数）。问题会创建大量浪费的空间。如果超过 M，则需要实施另一种策略。对于基于内存的实现，性能不是很好，但如果桶是基于磁盘的，则可以实现。对于分桶，λ > 1是可以的。但是，λ 越大，发生冲突的可能性就越高。λ > 1 保证至少会发生 1 次冲突（鸽巢原理）。这将提高运行时间... 阅读更多

寻找不等字母成本的最优前缀码的问题包括计算最小成本前缀码，其中编码字母表由不等成本（长度）字母组成，长度为 α 和 β，其中 α ≤ β。我们限制自己仅限于二叉树。该代码由一棵偏斜树表示，类似于霍夫曼树表示霍夫曼编码问题的解决方案。尽管存在相似之处，但不等字母成本的情况比经典的霍夫曼问题困难得多；尽管存在... 阅读更多