摘要： 本文对计算平面上n个线段所有交点的平面扫描算法及数据结构作了改进。若设k是线段集的交点个数,m是垂直扫描线在扫描过程中与线段集的最大交点数,则改进后的算法的计算时间为O(nlogm+klogm),占用存储空间O(m)。

关键词: 数据结构, 算法, 线段, 平面扫描

中图分类号: 

• TP391.4