# 数据结构知识 # 最小生成树 视频链接 他的作用即将一个带权连通无向图转换成一个树形结构，并且权值最低。 常用的算法有 Kruskal 算法和 Prim 算法 Prim 算法是从第一个点开始，然后每连通一条边，都将已经连通的点当作一个整体去找下一个链接当前整体的权值最小的边，去连接那个点。不能存在图。适用于点较少的图 Kruskal 算法是先把每个点都画出来，然后寻找权值最小的边相连，不能存在环 适用于边较少的图 # 英文单词对照 对角线： diagonal 角 corners 相邻的：adjacent 随机增量算法：Randomized Incremental Algorithm 转换...

# 为什么要用 因为如类似于最小生成树这样的问题，当量级上去了，时间复杂度也会以非常夸张的形式提升，所以有些时候，我们宁可牺牲一点选择近似的方式，但是时间复杂度会快非常多 # 两种近似方法 # 启发式 启发式方法在实际中很好用，比如用 AI、贪心、局部优化等等。但问题是 —— 你无法证明这个方法一定能给出好结果，有时候甚至什么都算不出来 # 近似算法 而我们要讲的，是有保证的近似算法。这些算法有一个好处 —— 无论多难的题，它至少不会比最好的答案差太多，比如最多差 2 倍。 但同时 如果我们只能证明他最多差 100 倍，那么这也就说明可能存在差 100...

# 📌 数学推导目标 我们希望算出： 对一个固定的查询点 qqq，在所有 n!n!n! 条线段插入顺序下，它的查询路径（走 DAG 的节点数）平均是多少？ # 🧱 定义记号 XiX_iXi​：第 iii 条线段插入时，是否导致查询路径中新增了一个节点。 是：Xi=1X_i = 1Xi​=1，否：Xi=0X_i = 0Xi​=0 那么 ∑i=1nXi\sum_{i=1}^n X_i∑i=1n​Xi​ 表示：最终查询路径长度 我们关心的是期望值：E[∑Xi]\mathbb{E}\left[\sum X_i\right]E[∑Xi​] # 🎯...

# 1. 平面点定位问题 首先代入日常生活，就如同我们使用地图软件一般，我们点击某个点的时候，我们需要快速判断出我们点的是哪个区间的点。 自然而然的可以想到的就是暴力法，即每次搜索点的时候都通过线性扫描扫描所有的点，但是这样的效率太低了，每次都需要 O (n) 的时间复杂度，所以接下来我们考虑别的方式 # 1.1 垂直切分法（Vertical Slab Decomposition） 如图所示，我们可以按照每个点所在的 y 轴进行切分，然后根据二分查找，第一次找出点所在的 slab。 然后，找出在哪个 slab...

# 🎯 1. 背景与目标 # 📌 应用场景 轨迹数据广泛存在于以下应用中： GPS 路径（车辆、手机用户行驶轨迹） 雷达 / 卫星跟踪（如台风移动路径） 动物迁徙轨迹（如候鸟、鲸鱼） 运动轨迹数据（如跑步者、球员移动） 这些轨迹数据常常由很多点组成，呈折线状。 # 🧠 分析目标： 从这些轨迹中提取有意义的行为模式，例如： 找出聚集区域（多个个体集中活动）； 分析路径形状（如迁徙路线）； 进行预测分析（如风暴路径预测）。 # ❓ 要解决的两个核心问题 相似性问题： 给定两条轨迹，如何判断它们的相似程度？ 哪些方法能更准确刻画...

# 1. 为什么需要逼近算法？ # 1.1 计算难度：NP-Hard 很多现实中的优化问题都是 NP-hard，即没有已知的多项式时间算法。 例如：Euclidean TSP（旅行商问题）、Quadratic Assignment（二次指派问题）等。 这些问题只能在小规模实例上通过精确算法解决。 # 1.2 运算成本高 即使问题不是 NP-hard，在高维空间或大规模数据下，精确算法也往往太慢。 举例： 2D 最小生成树：O(nlog⁡n)O(n \log n)O(nlogn) 高维 kkkD 最小生成树：O(n2)O(n^2)O(n2) 使用逼近算法可将其降至...

# Voronoi Diagram 基础讲解 # 什么是 Voronoi Diagram? 给定一个点集 P={p1,p2,…,pn}P = \{p_1, p_2, \dots, p_n\}P={p1​,p2​,…,pn​}，Voronoi 图是将平面划分为 nnn 个区域（称为 Voronoi Cells），每个区域对应一个点 pip_ipi​，使得该区域中任意一点 qqq 满足： dist(q,pi)<dist(q,pj)∀j≠i\text{dist}(q, p_i) < \text{dist}(q, p_j)...

# 1. 问题定义：什么是 Planar Point Location？ 目标：给定一个平面细分（由线段将平面划分成多个不重叠区域），我们希望预处理它，使得对于任意查询点 qqq，可以快速判断它位于哪个区域（face）中。 输入：包含 nnn 条边的平面细分 SSS。 查询：给定一个点 qqq，返回包含它的面。 # 2. 第一种方法：暴力线性扫描 思路：遍历所有面，检查查询点 qqq 是否落在其中。 做法： 对每个面进行点在多边形内的判断（如射线法或环绕数方法）。 时间复杂度： 每个面 O(k)O(k)O(k)，总共...

# 1. 点线对偶（Point-Line Duality） 点线对偶是计算几何中的一种基本变换思想，它允许我们在平面上将点与线互相转换，并在保持几何关系的前提下，从不同的角度简化问题。 # 1.1 什么是点线对偶 点线对偶（也称为几何对偶）是一种函数或映射，将平面中的一个几何对象（如点）转换为另一种对象（如直线），并且可以保持或反映其之间的几何关系，如： 点与直线的交关系； 点在线的上下方位置关系； 共线性、共点性等结构性质。 这种变换是一一对应的，即每个点对应唯一的一条线，反之亦然（在限定条件下）。 # 1.2...