Title: A Grid-based Algorithm for Determining Convex Hull of a Planar Set
Abstract: In this paper, a new algorithm is presented for determining the convex hull of a planar set. The computing method uses a grid array to divide the planar point set into lots of subsets so that the convex hull can be determined by a part of subsets which are at the edge of the planar point set, and then a simple polygon which contains all points of the planar point set is gained by some processes operating on those subsets in the anti-clockwise sequence, after that the convex hull is gotten by deleting the concave points from the simple polygon. The efficiency of the calculation is greatly improved owing to the operation kept in the points that are at the edge of the planar point set.The time complication of the algorithm in the worst condition is O(NlogN).
Publication Year: 2004
Publication Date: 2004-01-01
Language: en
Type: article
Access and Citation
Cited By Count: 1
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot