Title: A Sweep Algorithm for Finding the Convex Hull of a Line Segment Set in the Plane
Abstract: This paper first proves that a lower bound of the convex hull problem of a line segment set in the plane is O(nlogn). Its method is to connect the convex hull problem of a line segment set in the plane with the sorting problem, from the lower bound of the sorting problem we can infer the lower bound of the convex hull problem of a line segment set in the plane. Secondly an algorithm is presented for solving the convex hull problem of a line segment set in the plane, its basic idea is that the segments in the non-intersecting line segment set are sorted in the order of x and y coordinates of their endpoints, and the sequence of the line segments are resorted. Then the convex hull is partitionedly constructed by using a plane-sweep technique. The time complexity of this algorithm is O(nlogn).
Publication Year: 2003
Publication Date: 2003-01-01
Language: en
Type: article
Access and Citation
Cited By Count: 2
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot