Wang Xiaodong, Fu Qingxiang, Fan Qing, Wang Meiji. AN IMPROVED PLANE SWEEP ALGORITHM FOR LINE SEGMENT INTERSECTION PROBLEMSJ. Journal of Computer-Aided Design & Computer Graphics, 1996, 8(2): 87-94.
Citation:
Wang Xiaodong, Fu Qingxiang, Fan Qing, Wang Meiji. AN IMPROVED PLANE SWEEP ALGORITHM FOR LINE SEGMENT INTERSECTION PROBLEMSJ. Journal of Computer-Aided Design & Computer Graphics, 1996, 8(2): 87-94.
Wang Xiaodong, Fu Qingxiang, Fan Qing, Wang Meiji. AN IMPROVED PLANE SWEEP ALGORITHM FOR LINE SEGMENT INTERSECTION PROBLEMSJ. Journal of Computer-Aided Design & Computer Graphics, 1996, 8(2): 87-94.
Citation:
Wang Xiaodong, Fu Qingxiang, Fan Qing, Wang Meiji. AN IMPROVED PLANE SWEEP ALGORITHM FOR LINE SEGMENT INTERSECTION PROBLEMSJ. Journal of Computer-Aided Design & Computer Graphics, 1996, 8(2): 87-94.
AN IMPROVED PLANE SWEEP ALGORITHM FOR LINE SEGMENT INTERSECTION PROBLEMS
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,
DownLoad: