We present simple output-sensitive algorithms that construct the convex hull of a set of
n points in two or three dimensions in worst-case optimal
O (
n log
h) time and
O (n) space, where
h denotes the number of vertices of the convex hull.
This research was supported by a Killam Predoctoral Fellowship and an NSERC Postgraduate Scholarship.