JOURNAL OF COMPUTERS (JCP)

ISSN : 1796-203X

Volume : 3 Issue : 10 Date : October 2008

**An Isomorphic New Algorithm for Finding Convex Hull with a Maximum Pitch of the Dynamical **

Base Line Guided by Apexes Distributing Characteristics

Qihai Zhou, Tao Huang, and Hongyu Wu

Page(s): 12-19

Full Text: PDF (552 KB)

**Abstract**

In this paper, a representative algorithm convex hull with half-dividing and recurrence is

commented; and according to the isomorphic fundamental theorem of the convex hull construction,

and guided by the isomorphic distributing characteristics of a convex hull’s the apexes, a more

efficient new algorithm to find a convex hull based on the dynamical base line with a maximum pitch

of the dynamical base line is given. The general characters of the new algorithm are: 1) find out the

outside-most poles which are the leftmost, rightmost, topmost and bottommost points of the given

2D point set, i.e. the four initial poles which have the maximum or the minimum coordinate value of

the X or Y axis among all the points in the given 2D point set; 2) divide the original distributed

domain into four subdomains with the initial poles; 3) in every sub-domain, construct a current pole

with a maximum pitch to its base line based on the last pole got just dynamically and sequentially,

and draw the rims of this convex polygon with these poles for intelligent approximating for a convex

hull of the given 2D point set step by step.

**Index Terms**

isomorphic, convex hull algorithm, maximum pitch, dynamical base line, apexes distributing

characteristics

ISSN : 1796-203X

Volume : 3 Issue : 10 Date : October 2008

Base Line Guided by Apexes Distributing Characteristics

Page(s): 12-19

Full Text: PDF (552 KB)

commented; and according to the isomorphic fundamental theorem of the convex hull construction,

and guided by the isomorphic distributing characteristics of a convex hull’s the apexes, a more

efficient new algorithm to find a convex hull based on the dynamical base line with a maximum pitch

of the dynamical base line is given. The general characters of the new algorithm are: 1) find out the

outside-most poles which are the leftmost, rightmost, topmost and bottommost points of the given

2D point set, i.e. the four initial poles which have the maximum or the minimum coordinate value of

the X or Y axis among all the points in the given 2D point set; 2) divide the original distributed

domain into four subdomains with the initial poles; 3) in every sub-domain, construct a current pole

with a maximum pitch to its base line based on the last pole got just dynamically and sequentially,

and draw the rims of this convex polygon with these poles for intelligent approximating for a convex

hull of the given 2D point set step by step.

characteristics