是否存在经O(nlogn)预处理后线性时间完成平面点任意方向排序的算法？

• 需求为对平面点集，支持按任意线性函数a*x + b*y的取值，以O(n)线性时间完成排序，该排序等价于沿方向(a,b)的扫描线与点的相遇顺序
• 示例：点集包含(2,2)、(3,0)、(0,3)，按3x+2y排序的正确结果为[(0,3), (3,0), (2,2)]
• 预处理阶段允许非线性时间，最高可接受O(n²)复杂度，理想目标为O(n log n)；目前已知朴素枚举所有扫描线方向的方案预处理复杂度为O(n² log n)，核心疑问为是否存在O(n log n)的预处理方案，以及相关文献线索。

不存在满足「O(n log n)预处理 + 最坏情况O(n)查询」的通用算法，但存在接近该指标的实用方案，相关结论属于计算几何领域的经典研究范畴。

• 该问题的本质是点集的方向排序问题：两点的相对顺序仅在扫描线方向垂直于两点连线时翻转，整个点集总共有O(n²)种本质不同的排序结果。已有的复杂度下界证明显示，若要求最坏情况下线性时间输出排序结果，预处理的空间和时间复杂度下界为Ω(n²)，和朴素枚举方案的复杂度量级一致，不可能用O(n log n)的预处理覆盖所有可能的排序结果。
• 若不要求严格最坏情况O(n)查询，O(n log n)预处理的可行方案如下：
  • 预处理阶段用O(n log n)时间构建点集的凸层（Convex Layers，即逐层剥凸包得到的嵌套凸包结构），同时为每层凸包预存顶点的环形顺序索引
  • 查询给定线性函数方向时，从最外层凸包开始，每层用二分法找到该方向上的极值点，结合归并思路按投影值顺序合并各层点序列，得到最终排序结果。该方案在点分布均匀的场景下查询效率接近O(n)，仅在点集大量共线、凸层数量接近n的极端退化场景下，查询复杂度会退化到O(n log n)。
• 若接受查询阶段带O(log² n)的额外开销，可以通过分数级联优化凸包方向查询的跳转效率，实现渐进意义上O(n)级别的查询时间，这类结构属于半平面范围查询、动态凸包方向的经典研究内容。

• 计算几何通用教材《Computational Geometry: Algorithms and Applications》中对偶排列、凸层、方向极值查询的相关章节
• Chazelle在20世纪80年代关于范围查询、排序预处理的复杂度下界证明，明确了线性时间排序查询的预处理复杂度阈值
• 工程实现层面，预构建凸层+方向极值二分查找是目前图形学、地理信息处理中处理任意方向扫描线排序的最常用落地方案

内容的提问来源于stack exchange，提问作者timdrie