CHAN's PLANAR CONVEX HULL ALGORITHM: A Brief Survey and Sequential Experimental Comparison

AuthorSearch for:
ConferenceJournal of Scientific and Practical Computing: Part A, December 2006.
VolumeVolume 1, Number 1
Subjectplanar convex hull; design and analysis of algorithms; output-sensitive; Graham's Scan; Jarvis' March; Chan's Algorithm; conception et analyse d'algorithmes; adaptation à la sortie; algorithme de Graham; algorithme de Jarvis; algorithme de Chan
AbstractA study of some of the planar convex hull algorithms in existence, leading up to and includingChan's 1995 planar convex hull algorithm, is made. The algorithms include: i) Graham's 1972algorithm, ii) Jarvis' 1973 algorithm, and iii) Chan's 1995 algorithm. In addition, brief commentsare provided on the i) implementation work, including one variant of each of Graham's and Jarvis'algorithms, and four variants of Chan's algorithm, ii) testing for correctness of implementationand iii) simulation of point set data and the resulting empirical experimental results obtainedwithin the scope of the particular implementations.
Publication date
AffiliationNRC Institute for Information Technology; National Research Council Canada
Peer reviewedNo
NRC number48798
NPARC number5765625
Export citationExport as RIS
Report a correctionReport a correction
Record identifier8467bba2-749c-49d6-b27e-5d670a1efe70
Record created2009-03-29
Record modified2016-05-09
Bookmark and share
  • Share this page with Facebook (Opens in a new window)
  • Share this page with Twitter (Opens in a new window)
  • Share this page with Google+ (Opens in a new window)
  • Share this page with Delicious (Opens in a new window)
Date modified: