线段相交问题的平面扫描型改进算法

AN IMPROVED PLANE SWEEP ALGORITHM FOR LINE SEGMENT INTERSECTION PROBLEMS

摘要: 本文对计算平面上n个线段所有交点的平面扫描算法及数据结构做了改进.若设这n个线段的交点总数为k,这n个线段中与垂直扫描线相交的最多个数为m,则改进后的算法的计算时间为O(nlogm+klogm),占用存储空间为O(m).

Abstract: This paper presents an improved data structure of the sweeping plane algorithm for line segment intersection of size n.The time and space complexities of the improved algorithm for line segment intersection are O(nlogm+klogm) and O(m),where k is the number of intersecting pairs and m is the maximum number of line segments intersecting with the sweeping line,