“解码时沿记录指针恢复偏离序列,再插入唯一树链。若显式输出总弧数为L,另付O(L+k)时间;零边游走也要一条分帧记录。这正是输出敏感计费所要求的输出接口区别。”
形式陈述
通常的时间复杂度把同样大小的输入合并取最坏情况。输出敏感分析进一步固定计算模型、输入编码与输出表示,令
这里的
数据结构查询还要拆开预处理与单次成本:先用
输出敏感界不必是
直觉
许多输入对象不会成为答案,却必须被读取或用于排除。分析时给这两类工作分别记账:定位、搜索或预处理支付“找到答案”的成本;每报告一项,再支付与这一项有关的成本。关键不是在公式末尾添一个
这也解释了为什么“小答案”有时仍不便宜。即使凸包只有三个极点,算法通常仍须查看所有输入点,确认没有遗漏一个外部点;输出敏感性会减少超过这份输入检查的额外工作,而不会自动免除读取输入。
例子与边界
区间查询中,停止比较记给谁
在中心区间树的一个节点,中心为
查询
| 所读左端点 | 比较 | 动作 |
|---|---|---|
| 2 | 报告 |
|
| 7 | 报告 |
|
| 9 | 停止扫描 |
最后一项未被输出,但并非没有成本。每个访问节点至多有一次这样的停止比较,其余被读项都各自对应一个输出。随后只进入左子树,右子树的区间全在中心右侧,不可能含
静态构造可用端点中位数保证对数树高;若动态版本预建含
不知道凸包大小时怎样猜
考虑
- 分成
组,各组至多 点;分别计算只保留极点的局部凸包并按环序存储,总计 。 - 从全局极点出发;每一步在各局部凸包上求支持切线,以二分切线查询取得该组的候选,再从这些候选中选出下一个全局极点。若允许共线点,组内切线选择和组间候选比较都在从当前顶点出发方向相同的候选中选择距离最远者,跳过同一条边上的非极点。每步成本为
。 - 回到起点即输出整个环;执行
步仍未闭合则返回incomplete,不能把这段前缀当作最终凸包。
每一步选的是支持整组、进而支持全部输入的下一条边,因此已生成的前缀始终是全局边界的一段。取
未知
设首次成功在第
例如
上述最远点规则也处理只有部分点共线的情形。例如从
有限解枚举把“总输出多项式”进一步分成首项等待、相邻项间隔、结束等待与工作空间。先等
推论与应用
Aho–Corasick 自动机的输出链把每个报告步骤记给一个匹配,因而扫描是
扫描线报告
参考资料
- Timothy M. Chan,Optimal Output-Sensitive Convex Hull Algorithms in Two and Three Dimensions,Discrete & Computational Geometry 16(4),1996,pp. 361–368,§2 的分组、切线与双指数猜测,§4 的退化处理及复用改进。
- Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars,Computational Geometry: Algorithms and Applications,第 3 版,Springer,2008,§10.1 的 interval tree 与报告查询。