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

From National Research Council Canada

AuthorSearch for:
TypeArticle
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
Abstract
A 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
LanguageEnglish
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
Date modified:
Report a problem on this page