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

From National Research Council Canada

AuthorSearch for:
FormatText, Article
Journal titleJournal of Scientific and Practical Computing: Part A
Volume1
Issue1
Subjectplanar convex hull; design and analysis of algorithms; output-sensitive; Graham's Scan; Jarvis' March; Chan's Algorithm
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 numberNRCC 48798
NPARC number5765625
Export citationExport as RIS
Report a correctionReport a correction
Record identifier8467bba2-749c-49d6-b27e-5d670a1efe70
Record created2009-03-29
Record modified2020-04-22
Report a problem on this page
Date modified: