New Recurrence Algorithm for Finding Convex Hull Based on Maximum Current Base Line Vertical Drop
Tao Huang · 2008
In this paper,the domain state natures and vertical drop characters of the apexes of a convex hull are found and proofed in the lead;a creative new thought for constructing an algorithm with the maximum current base line vertical drop is given;a new recurrence algorithm of finding convex hull based on maximum current base line vertical drop which is better than the quick hull algorithm for convex hulls as one of the most excellent convex hull algorithms is advanced;the potentialities to reform into parallel algorithm are pointed out.The general characters of this new recurrence algorithm are:1) Find out all most-outside points(its total lower limit is 3,and upper limit is 8) as the initial apexes of a convex hull.2) After deleting all interior points covered by the most-outside points' convex polygon,the rest points' domain is divided into some initial sub-domains(its total lower limit is 0,and upper limit is 4).3) 1st,to every not empty current initial sub-domain,call separately the recurrence procedure sub-algorithm to find out the maximum current base vertical drop points of the current sub-domain(its total lower limit is 1,and upper limit is 2) as the convex hull apexes;2nd,after deleting all interior points covered by the current base's convex polygon,the rest points' sub-domain is divided into some smaller sub-domains(its total lower limit is 0,and upper limit is 2);3rd,to every not empty smaller current sub-domain,call separately the recurrence procedure sub-algorithm to find out the maximum current base vertical drop points of the current sub-domain as the convex hull apexes.