扫描线算法如何将二维问题降维成一维从天际线到矩形面积的LeetCode完整通关指南
扫描线算法是计算几何中最优雅的算法范式之一。它的核心思想简单得令人惊讶：用一条假想的线扫过整个平面，只在关键点停下来处理。这个朴素的想法却催生了计算复杂度理论的重大突破。1976年，Michael Shamos 和 Dan Hoey 发表了标志性的线段相交检测算法，证明了扫描线结合平衡二叉树可以在 $O(N \log N)$ 时间内判断 $N$ 条线段是否存在交点——这在当时是革命性的结果。随后，Bentley 和 Ottmann 将其扩展为报告所有交点的算法，Fortune 在 1986 年用扫描线构造 Voronoi 图，这些工作奠定了计算几何作为独立学科的基础。 ...