Title: Optimum Algorithm for Constructing Convex Hull of Planar Point Set Utilizing Plus or Minus Characteristic of Demarcation
Abstract: Constructing convex hull of planar point set is a basic algorithm in computational geometry.Although the number of current algorithms is increasing,most of them are quite complex.In order to reduce the algorithm complexity,the paper starts with analyzing the Plus or Minus Characteristic of Demarcation of a straight line.The purpose of step is to partition planar point set and to simplify the calculation distance from a point to a straight line.Then an improved algorithm is given which is seeking the convex hull of an arbitrarily distributing planar point set.This algorithm is simpler and the speed is faster than the popular algorithm which has adopted forward-backward method in searching convex hull.Our algorithm is also superior to the traditional algorithm.In particular it is unnecessary to compute the angle,Euclidean distance.Applying the algorithm to seek the convex hull of an arbitrarily distributing planar point set can obtain accurate,results through only addition,subtraction,multiplication and comparision.The method reduces the computing time for of each step therefore it is an optimal algorithm because of its efficiency.
Publication Year: 2007
Publication Date: 2007-01-01
Language: en
Type: article
Access and Citation
Cited By Count: 3
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot