An Efficient Algorithm for the Convex Hull of Planar Point Set
Guangquan Fan · Geography and Geo-Information Science · 2006
This paper presents and realizes an efficient algorithm for the convex hull of planer point set.It is Eight Direction Extreme Value Fast Convex Hull Algorithm.The extreme values on eight directions(east,west,south,north,east-south,west-south,east-north,west-north)are found fleetly after scanning the point set.Thus an initial convex hull that is closer to the real one is built.So more inner points can be excluded during the next scanning.During the second scanning,not only all the inner points of the initial convex hull are excluded,but also every outside point is associated with its unique initial convex hull edge.Thus,the searching of the farthest point is limited in its outside point set.In addition,when a point is judged as an outside point of a sub convex hull edge,the information of the farthest point of the sub convex hull edge is saved,so the distance calculating for searching the farthest point is avoided.All these make the algorithm more efficient.The space complexity of the algorithm is O(N).Although its time complexity can not break through the low limit of O(Nlog N)in the worst case,its expected time complexity is already linear.Additionally,the algorithm can be generalized to three or high dimension easily.