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