平面扫描算法：Fortune算法与Voronoi图构造

"这篇内容来自计算几何领域的著作，主要探讨了如何构建Voronoi图，这是一种在计算几何中广泛使用的数据结构，常用于各种应用，包括GIS（地理信息系统）。文章介绍了Voronoi图的构造方法，特别是通过平面扫描（plane sweep）算法，也称为Fortune算法，可以在O(nlogn)的时间复杂度内完成，这是最优的时间复杂度，因为Voronoi图构造问题可以等价于实数排序问题，其下限是Ω(nlogn)。 在构建Voronoi图的过程中，作者提到使用扫描线自上而下扫过平面，扫描线移动时，需要维护与之相关的Voronoi图信息。事件点（event point）是在扫描过程中需要更新信息的位置。对于Voronoi图的构造，关键在于理解当扫描线到达Voronoi单元的高顶点时，需要考虑上方和下方基点的影响。在扫描线l上方，称为l+的闭半平面内的Voronoi图部分会保持不变，对于这些点，可以确定最近的基点。 文章还涉及了计算几何的一些其他主题，如线段求交、多边形三角剖分、线性规划、正交区域查找、点定位以及排列与对偶问题，这些都是计算几何中核心的概念和技术。这些内容对于理解和解决实际问题，如数据库查询、图形渲染、三维建模等具有重要意义。" 知识点： 1. Voronoi图：是一种几何分割，每个点的邻域由与其距离最近的种子点决定，常用于地理信息系统和路径规划。 2. Fortune算法：一种平面扫描算法，用于在O(nlogn)时间内构建Voronoi图，是最优算法。 3. 平面扫描算法：使用扫描线自上而下扫过平面，维护与扫描线相关的信息，事件点是需要更新信息的位置。 4. 事件点：扫描线与Voronoi边的交点，或基点穿过扫描线的时刻。 5. 扫描线l+：扫描线上方的闭半平面，其中Voronoi图的部分是固定的，不随扫描线移动而改变。 6. Voronoi单元的高顶点：扫描线到达Voronoi单元的边界点，可能需要考虑下方基点的影响。 7. 实数排序与Voronoi图构造的关系：Voronoi图构造问题的复杂度下限是Ω(nlogn)，因为可以归约为实数排序问题。 8. 计算几何的应用领域：包括数据库查询、三维建模、光线追踪、地形分析等。 9. 其他计算几何主题：线段求交、多边形三角剖分、线性规划、正交区域查找、点定位等，都是计算几何的基本工具。