Author Login Chief Editor Login Reviewer Login Editor Login Remote Office

›› 1994, Vol. 20 ›› Issue (S1): 76-81.

• Papers • Previous Articles     Next Articles

  

  • Published:1994-12-29

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

王晓东,傅清祥,范庆,王梅集   

  1. 福州大学计算机系 福州 350002,福州大学计算机系 福州 350002,福州大学计算机系 福州 350002,福州大学计算机系 福州 350002

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

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

CLC Number: